﻿#define _CRT_SECURE_NO_WARNINGS 1


//int main()
//{
//	int num;
//	scanf("%d", &num);
//	if (num >= 0 && num <= 1)
//	{
//		printf("Today, I ate %d apple.", num);
//	}
//	else if (num > 1 && num <= 100)
//	{
//		printf("Today, I ate %d apples.", num);
//	}
//	return 0;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	if (n >= 1 && n <= 100)
//	{
//		if ((5 * n) > (3 * n + 11))
//		{
//			printf("Luogu");
//		}
//		else if ((5 * n) < (3 * n + 11))
//		{
//			printf("Local");
//		}
//	}
//	return 0;
//}
//int main()
//{
//	double m, h;
//	scanf("%lf %lf", &m, &h);
//	if (m >= 40 && m <= 120 && h >= 1.4 && h <= 2.0)
//	{
//		double BIM = m / (h * h);
//		if (BIM < 18.5)
//		{
//			printf("Underweight");
//		}
//		else if (BIM >= 18.5 && BIM < 24)
//		{
//			printf("Normal");
//		}
//		else if (BIM >= 24)
//		{
//			std::cout << BIM << endl << "Overweight" << endl;
//		}
//	}
//}
//int main()
//{
//	int a, b, c;
//	scanf("%d %d %d", &a, &b, &c);
//	int t = 0;
//	if (a > b)
//	{
//		t = b;
//		b = a;
//		a = t;
//	}
//	if (a > c)
//	{
//		t = c;
//		c = a;
//		a = t;
//	}
//	if (c < b)
//	{
//		t = b;
//		b = c;
//		c = t;
//	}
//	printf("%d %d %d", a, b, c);
//	return 0;
//}
//#include <stdio.h>
//
//int sum(int n);
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    printf("%d\n", sum(n));
//    return 0;
//}
//
//int sum(int n)
//{
//    int add = 0;
//    for (int i = n; i > 0; i--)
//    {
//        add += i;
//    }
//    return add;
//}
//#include <stdio.h>
//
//int Ack(int m, int n);
//
//int main()
//{
//    int m, n;
//
//    scanf("%d %d", &m, &n);
//    printf("%d\n", Ack(m, n));
//
//    return 0;
//}
//
//int Ack(int m, int n)
//{
//    if (m == 0)
//    {
//        return (n + 1);
//    }
//    else if (n == 0 && m > 0)
//    {
//        Ack(m - 1, 1);
//    }
//    else if (m > 0 && n > 0) {
//        Ack(m - 1, Ack(m, n - 1));
//    }
//}
// 
//#include <stdio.h>
//#include<math.h>
//
//double calc_pow(double x, int n);
//
//int main()
//{
//    double x;
//    int n;
//
//    scanf("%lf %d", &x, &n);
//    printf("%.0f\n", calc_pow(x, n));
//
//    return 0;
//}
//
//double calc_pow(double x, int n)
//{
//    if (n > 1)
//    {
//        x *= calc_pow(x, n - 1);
//    }
//    else
//        return x;
//    return x;
//}

//#include <stdio.h>
//
//int f(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    printf("%d\n", f(n));
//
//    return 0;
//}
//
//int f(int n)
//{
//    int x = 0;
//    if (n == 0)
//    {
//        return 0;
//    }
//    else if (n==1)
//    {
//        return 1;
//    }
//    else
//    {
//        x += f(n - 1) + f(n - 2);
//    }
//    return x;
//}

//#include <stdio.h>
//
//void printdigits(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    printdigits(n);
//
//    return 0;
//}
//int i = 0;
//void printdigits(int n)
//{
//    int t = 0;
//    if (n != 0)
//    {
//        i++;
//        t = n % 10;
//        printdigits(n / 10);
//        printf("%d\n", t);
//    }
//    else if (n == 0 && i == 0)
//    {
//        printf("0");
//    }
//    
//}
//#include <stdio.h>
//#include <math.h>
//
//int search(int n);
//
//int main()
//{
//    int number;
//
//    scanf("%d", &number);
//    printf("count=%d\n", search(number));
//
//    return 0;
//}
//
//int search(int n)
//{
//    int k = 0;
//    int t = 0;
//    int q = 0;
//    int p = 0;
//    int m = 0;
//    if (n >= 121)
//    {
//        for (int i = 121; i <= n; i++)
//        {
//            if (pow((int)sqrt(i), 2)==i)
//            {
//                m = i;
//                t = i % 10;
//                i /= 10;
//                p = i % 10;
//                i /= 10;
//                q = i % 10;
//                i = m;
//                if (p == q || p == t || q == t)
//                {
//                    k++;
//                }
//            }
//        }
//    }
//    return k;
//}

//int main()
//{
//    for (int i = 3; i < 100; i+=3)
//    {
//        printf("%d ", i);
//     }
//    return 0;
//}
//int main()
//{
//	int a = 0, b = 0, c = 0;
//	int t = 0;
//	scanf("%d %d %d", &a, &b, &c);
//	if (a < b)
//	{
//		t = a;
//		a = b;
//		b = t;
//	}
//	if (a < c)
//	{
//		t = a;
//		a = c;
//		c = t;
//	}
//	if (c > b)
//	{
//		t = c;
//		c = b;
//		b = t;
//	}
//	printf("%d %d %d", a, b, c);
//	return 0;
//}
//int main()
//{
//	int a, b, c;
//	while (scanf("%d %d %d", &a, &b, &c) == 3)
//	{
//		if (a < (b + c) && b < (a + c) && c < (a + b))
//		{
//			if (a == b && b == c)
//			{
//				printf("Equilateral triangle!\n");
//			}
//			else if (a == b || a == c || b == c)
//			{
//				printf("Isosceles triangle!\n");
//			}
//			else
//				printf("Ordinary triangle!\n");
//		}
//		else
//			printf("Not a triangle!\n");
//	}
//	return 0;
//}.
//#include<math.h>
//int main()
//{
//    double add = 0;
//    for (double i = 1; i <= 100; i++)
//    {
//        int n = i + 1;
//        add += pow(-1,n) / i;
//    }
//    printf("%lf", add);
//    return 0;
//}
//int main()
//{
//	int num = 0;
//	for (int i = 9; i < 100; i += 10)
//	{
//		num++;
//	}
//	printf("%d", num);
//	return 0;
//}
//int main()
//{
//	for (int i = 1000; i <= 2000; i++)
//	{
//		if ((i % 4 == 0 && i % 100 != 0) || (i % 400 == 0))
//		{
//			printf("%d\n", i);
//		}
//	}
//	return 0;
//}
//#include <stdio.h>
//
//int main() {
//    int numbers[10];  // 存储 10 个整数的数组
//    int i;
//    int max;
//
//    printf("请输入 10 个整数：\n");
//
//    // 获取用户输入的 10 个整数
//    for (i = 0; i < 10; i++) {
//        printf("请输入第 %d 个整数：", i + 1);
//        scanf("%d", &numbers[i]);
//    }
//
//    // 假设第一个数为最大值
//    max = numbers[0];
//
//    // 遍历数组，找到最大值
//    for (i = 1; i < 10; i++) {
//        if (numbers[i] > max) {
//            max = numbers[i];
//        }
//    }
//
//    // 输出最大值
//    printf("最大值为：%d\n", max);
//
//    return 0;
//}

//int main()
//{
//	int year, month;
//	scanf("%d %d", &year, &month);
//	if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
//	{
//		printf("31");
//	}
//	else if (month == 2)
//	{
//		if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
//		{
//			printf("29");
//		}
//		else
//			printf("28");
//	}
//	else
//		printf("30");
//	return 0;
//}

//int main()
//{
//	int a, b, c = 0, d = 0;
//	int arr[7] = { 0 };
//	int max = 0;
//	for (int i = 0; i < 7; i++)
//	{
//		scanf("%d %d", &a, &b);
//		arr[i] = a + b;
//	}
//	int j = 0;
//	for ( j = 0; j < 7; j++)
//	{
//		
//		if (arr[j] > 8)
//		{
//			c++;
//			if (max < arr[j])
//			{
//				d = j;
//				max = arr[j];
//			}
//		}
//	}
//	if (c != 0)
//	{
//		printf("%d", d + 1);
//	}
//	else
//		printf("0");
//	return 0;
//}

//int main()
//{
//	int n;
//	scanf("%d", &n);
//	unsigned int num, price,num1,price1;
//	unsigned int a[3] = { 0 };
//	for (int i = 0; i < 3; i++)
//	{
//		scanf("%u %u", &num, &price);
//		num1 = num,
//		price1 = price;
//		for (int j = 1; num < n; j++)
//		{
//			price = price1 * j;
//			num = num1 * j;
//		}
//		a[i] = price;
//	}
//	unsigned int min = a[0];
//	for (int i = 0; i < 3; i++)
//	{
//		if (min > a[i])
//		{
//			min = a[i];
//		}
//	}
//	printf("%u", min);
//	return 0;
//}

//#include <stdio.h>
//int main() {
//	int i, a, b, c, n;
//	int ma, m = 0;
//	scanf("%d", &n);
//	for (i = 1; i < 4; i++) {
//		scanf("%d %d", &a, &b);//输入一盒的个数和价格
//		if (n % a > 0) {//判断和要买的盒数 
//			c = n / a + 1;
//		}
//		else {
//			c = n / a;
//		}
//		ma = b * c;//要多少钱 
//		if (ma < m || m == 0) {//m==0 使第一次输入的数据通过判断 
//			m = ma;
//		}
//	}
//	printf("%d", m);
//	return 0;
//}

//#include <stdio.h>
//#include<math.h>
//double fn(double x, int n);
//
//int main()
//{
//    double x;
//    int n;
//
//    scanf("%lf %d", &x, &n);
//    printf("%.2f\n", fn(x, n));
//
//    return 0;
//}
//
//int a = -1;
//double add;
//double m;
//double fn(double x, int n)
//{
//    if (n == 1)
//    {
//        return x;
//    }
//    else
//    {
//        return x - fn(x, n - 1) * x;
//    }
//}

//#include <stdio.h>
//
//void dectobin(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    dectobin(n);
//
//    return 0;
//}
//
//void dectobin(int n)
//{
//    if (n == 0)
//    {
//        printf("0");
//        return ;
//    }
//    else if ( n == 1 )
//    {
//        printf("1");
//        return ;
//    }
//    dectobin(n / 2);
//    printf("%d", n % 2);
//}

//#include <stdio.h>
//
//struct complex {
//    int real;
//    int imag;
//};
//
//struct complex multiply(struct complex x, struct complex y);
//
//int main()
//{
//    struct complex product, x, y;
//
//    scanf("%d%d%d%d", &x.real, &x.imag, &y.real, &y.imag);
//    product = multiply(x, y);
//    printf("(%d+%di) * (%d+%di) = %d + %di\n",
//        x.real, x.imag, y.real, y.imag, product.real, product.imag);
//
//    return 0;
//}
//
//struct complex multiply(struct complex x, struct complex y)
//{
//    struct complex p = { x.real * y.real - x.imag * y.imag,x.real * y.imag + x.imag * y.real };
//    return p;
//}





                               //6 - 10 按等级统计学生成绩




//#include <stdio.h>
//#define MAXN 10
//
//struct student {
//    int num;
//    char name[20];
//    int score;
//    char grade;
//};
//
//int set_grade(struct student* p, int n);
//
//int main()
//{
//    struct student stu[MAXN], * ptr;
//    int n, i, count;
//
//    ptr = stu;
//    scanf("%d\n", &n);
//    for (i = 0; i < n; i++) {
//        scanf("%d%s%d", &stu[i].num, stu[i].name, &stu[i].score);
//    }
//    count = set_grade(ptr, n);
//    printf("The count for failed (<60): %d\n", count);
//    printf("The grades:\n");
//    for (i = 0; i < n; i++)
//        printf("%d %s %c\n", stu[i].num, stu[i].name, stu[i].grade);
//    return 0;
//}
//
//int l;
//int set_grade(struct student* p, int n)
//{
//    if (n == 0)
//    {
//        return 0;
//    }
//    if (p->score >= 85 && p->score <= 100)
//    {
//        p->grade = 'A';
//        set_grade(p + 1, n - 1);
//    }
//    else if (p->score >= 70 && p->score <= 84)
//    {
//        p->grade = 'B';
//        set_grade(p + 1, n - 1);
//    }
//    else if (p->score >= 60 && p->score <= 69)
//    {
//        p->grade = 'C';
//        set_grade(p + 1, n - 1);
//    }
//    else
//    {
//        p->grade = 'D';
//        l++;
//        set_grade(p + 1, n - 1);
//    }
//    return l;
//}


                                          //7 - 1 计算职工工资

//struct fn {
//	char name[10];
//	float j;
//	float f;
//	float z;
//}x;
//
//
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	struct fn x;
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%s %f %f %f", x.name, &x.j, &x.f, &x.z);
//		float k = x.j + x.f - x.z;
//		printf("%s %.2f\n", x.name, k);
//	}
//	return 0;
//}


                                         //7 - 2 时间换算
//struct fn {
//    int hour;
//    int min;
//    int s;
//    int s1;
//}x;
//
//int main()
//{
//    struct fn x;
//    scanf("%d:%d:%d\n%d", &x.hour, &x.min, &x.s, &x.s1);
//    x.s += x.s1;
//    if ( x.s >= 60)
//    {
//        x.s = x.s - 60;
//        x.min += 1;
//        if (x.min == 60)
//        {
//            x.hour += 1;
//            if (x.hour == 24)
//            {
//                x.hour = 0;
//            }
//            x.min = 0;
//        }
//    }
//
//    printf("%02d:%02d:%02d", x.hour, x.min, x.s);
//    return 0;
//}



                                          //7 - 3 计算平均成绩
//struct fn {
//    char num[10];
//    char name[10];
//    int grade;
//};
//
//int main() 
//{
//    struct fn x[50];
//    int n;
//    double average = 0, add = 0;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%s %s %d", x[i].num, x[i].name, &x[i].grade);
//        add += x[i].grade;
//    }
//    average = add / n;
//    printf("%.2lf\n", average);
//    for (int i = 0; i < n; i++)
//    {
//        if (x[i].grade < average)
//        {
//            printf("%s %s\n", x[i].name, x[i].num);
//        }
//    }
//    return 0;
//}



                                          // 7 - 4 查找书籍
//struct fn {
//    char name[30];
//    double price;
//};
//int main()
//{
//    struct fn x[10];
//    int n, p = 0, q = 0;
//    double min, max;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        getchar();
//        fgets(x[i].name, sizeof(x[i].name), stdin);
//        x[i] .name[strcspn(x[i].name, "\n")] = '\0';
//        scanf("%lf", &x[i].price);
//    }
//    min = x[0].price;
//    max = x[0].price;
//    for (int i = 0; i < n; i++)
//    {
//        if (max < x[i].price)
//        {
//            p = i;
//            max = x[i].price;
//        }
//        if (min > x[i].price)
//        {
//            q = i;
//            min = x[i].price;
//        }
//    }
//    printf("%.2lf, %s\n", x[p].price, x[p].name);
//    printf("%.2lf, %s\n", x[q].price, x[q].name);
//}



                                          //九*九乘法表
//int main()
//{
//    int a[9] = { 1,2,3,4,5,6,7,8,9 };
//    int b[9] = { 1,2,3,4,5,6,7,8,9 };
//    for (int i = 0; i < 9; i++)
//    {
//        for (int j = i; j < 9; j++)
//        {
//            printf("%d * %d = %d    ", a[i], b[j], a[i] * b[j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}


                                          //最大公约数
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int t = 0;
//    while (b)
//    {
//        t = a % b;
//        a = b;
//        b = t;
//    }
//    printf("%d", a);
//    return 0;
//}


                                          //打印素数
//#include<math.h>
//int main()
//{
//    int i = 0;
//    int j = 0;
//    for ( i = 100; i <= 200; i++)
//    {
//        for ( j = 2; j <= sqrt(i); j++)
//        {
//            if (i % j == 0)
//            {
//                break;
//            }
//        }
//        if (j > sqrt(i))
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}


                                           //7-5 有理数比较
//struct fn {
//    int a;
//    int b;
//};
//
//int main()
//{
//    struct fn p, l;
//    scanf("%d/%d %d/%d", &p.a, &p.b, &l.a, &l.b);
//    double c, d;
//    c = (double)(p.a) / p.b;
//    d = (double)(l.a) / l.b;
//    if (c > d)
//    {
//        printf("%d/%d > %d/%d", p.a, p.b, l.a, l.b);
//    }
//    else if (c < d)
//    {
//        printf("%d/%d < %d/%d", p.a, p.b, l.a, l.b);
//    }
//    else if (c == d)
//    {
//        printf("%d/%d = %d/%d", p.a, p.b, l.a, l.b);
//    }
//    return 0;
//}


                                           //7-6 平面向量加法
//struct fn {
//    double a;
//    double b;
//};
//
//#include<math.h>
//
//int main()
//{
//    struct fn p, l;
//    scanf("%lf %lf %lf %lf", &p.a, &p.b, &l.a, &l.b);
//    double c, d;
//    c = p.a + l.a;
//    d = p.b + l.b;
//    if (fabs(c) < 0.05)//控制不输出-0.0
//    {
//        c = 0.0;
//    }
//    if (fabs(d) < 0.05)//控制不输出-0.0
//    {
//        d = 0.0;
//    }
//    printf("(%.1lf, %.1lf)", c, d);
//    return 0;
//}


                                           //P5717 【深基3.习8】三角形分类
//#include<stdio.h>
//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    if ((a + b > c) && (a + c > b) && (b + c > a))
//    {
//        if (a*a == b*b+c*c || b*b == a*a+c*c || c*c == a*a+b*b)
//        {
//            printf("Right triangle\n");
//        }
//        else if (a * a > b * b + c * c || b * b > a * a + c * c || c * c > a * a + b * b)
//        {
//            printf("Obtuse triangle\n");
//        }
//        else 
//        {
//            printf("Acute triangle\n");
//        }
//
//        if (a == b || b == c || c == a)
//        {
//            printf("Isosceles triangle\n");
//        }
//        if (a == b && b == c )
//        {
//            printf("Equilateral triangle\n");
//        }
//    }
//    else
//    {
//        printf("Not triangle\n");
//    }
//    return 0;
//}


                                           //P1422 小玉家的电费
//int main()
//{
//    unsigned int i;
//    scanf("%d", &i);
//    double a, b, c, s;
//    a = 150 * 0.4463;
//    b = 250 * 0.4663;
//    c = (i - 400) * 0.5663;
//    if (i >= 0 && i <= 150)
//    {
//        s = i * 0.4463;
//    }
//    else if (i > 150 && i <= 400)
//    {
//        b = (i - 150) * 0.4663;
//        s = a + b;
//    }
//    else
//    {
//        s = a + b + c;
//    }
//    printf("%.1lf", s);
//    return 0;
//}


                                           //P1424 小鱼的航程（改进版）
//int main()
//{
//    int a, b, s = 0;
//    scanf("%d %d", &a, &b);
//    for (int i = 0; i < b; i++,a++)
//    {
//        if (a % 6 == 0 || a % 7 == 0)
//        {
//            if (a % 7 == 0)
//            {
//                a = 0;
//            }
//            continue;
//        }
//        else
//        {
//            s += 250;
//        }
//    }
//    printf("%d", s);
//    return 0;
//}


                                           //P1888 三角函数
//int fn(int x,int y);
//
//
//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    double d, e, f;
//    int max = a;
//    if (max < b)
//    {
//        max = b;
//    }
//    if (max < c)
//    {
//        max = c;
//    }
//    d = (double)a / max;
//    e = (double)b / max;
//    f = (double)c / max;
//    int n = a;
//    double min = d;
//    if (min > e)
//    {
//        n = b;
//        min = e;
//    }
//    if (min > f)
//    {
//        n = c;
//        min = f;
//    }
//    int m = fn(n, max);
//    n = n / m;
//    max = max / m;
//    printf("%d/%d", n, max);
//}
//
//int fn(int x, int y)
//{
//    int t;
//    while (x)
//    {
//        t = y % x;
//        y = x;
//        x = t;
//    }
//    return y;
//}



                                           //P1046 [NOIP2005 普及组] 陶陶摘苹果
//int main()
//{
//    int a[10];
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int hight;
//    scanf("%d", &hight);
//    int h = hight + 30;
//    int s = 0;
//    for (int i = 0; i < 10; i++)
//    {
//        if (a[i] <= h)
//        {
//            s++;
//        }
//    }
//    printf("%d", s);
//    return 0;
//}


                                            //P4414 [COCI2006-2007#2] ABC
//int main()
//{
//    int a, b, c, t;
//    scanf("%d %d %d", &a, &b, &c);
//    char l[4];
//    getchar();
//    //for (int i = 0; i < 3; i++)
//    //{
//    scanf("%s", l);
//    //}
//    if (c < a)
//    {
//        t = c;
//        c = a;
//        a = t;
//    }
//    if (c < b)
//    {
//        t = c;
//        c = b;
//        b = t;
//    }
//    if (a > b)
//    {
//        t = a;
//        a = b;
//        b = t;
//    }
//    for (int i = 0; l[i] != 0; i++)
//    {
//        /* if (i != 0)
//         {
//             printf(" ");
//         }*/
//        switch (l[i])
//        {
//        case 'A':
//            printf("%d ", a);
//            break;
//        case 'B':
//            printf("%d ", b);
//            break;
//        case 'C':
//            printf("%d ", c);
//            break;
//        }
//    }
//    return 0;
//}


                                           //P1055 [NOIP2008 普及组] ISBN 号码
//int fn(char ch);
//
//
//int main()
//{
//    char k[13];
//    int x, add = 0;
//    int n = 0;
//    for (int i = 0; i < 13; i++)
//    {
//        scanf("%c", &k[i]);
//    }
//    for (int i = 0; i < 12; i++)
//    {
//        if (k[i] >= '0' && k[i] <= '9')
//        {
//            x = fn(k[i]);
//            add += x * n;
//            n++;
//        }
//    }
//    char v = '0';
//    if (add % 11 == 10)
//    {
//         v = 'X';
//    }
//    else
//         v = add % 11 + 47;
//    if (v == k[12])
//    {
//        printf("Right");
//    }
//    else
//    {
//        k[12] = v ;
//        for (int i = 0; i < 13; i++)
//        {
//            printf("%c", k[i]);
//        }
//    }
//    return 0;
//}
//
//int fn(char ch)
//{
//    int a = ch - '0';
//    return a;
//}



                                           //【一维数组】输入10个整数，求平均值
//int main()
//{
//    int a[10] = { 0 };
//    double add = 0;
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//        add += a[i];
//    }
//    printf("%lf", add / 10);
//    return 0;
//}


                                            //打印用“*”组成的X形图案
//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1)
//    {
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (i == j || i + j == n - 1)
//                {
//                    printf("*");
//                }
//                else
//                    printf(" ");
//            }
//            printf("\n");
//        }
//        
//    }
//    return 0;
//}


                                             //打印用“*”组成的“空心”正方形图案
//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1)
//    {
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (i == 0 || j == 0 || j == n - 1 || i == n - 1)
//                    printf("* ");
//                else
//                    printf("  ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


                                             //BC107 矩阵转置
//int main()
//{
//    int a[10][10];
//    int n, m;
//    scanf("%d %d", &n, &m);
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            printf("%d ", a[j][i]);
//        }
//        printf("\n");
//    }
//    return 0;
//}


                                             //BC92 逆序输出
//int main()
//{
//    int a[10];
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    for (int i = 9; i >= 0; i--)
//    {
//        printf("%d ", a[i]);
//    }
//    return 0;
//}



                                             //BC100 有序序列合并
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    int a[1000], b[1000];
//    int arr[2000];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//        arr[i] = a[i];
//    }
//    for (int j = 0; j < m; j++)
//    {
//        scanf("%d", &b[j]);
//        arr[n + j] = b[j];
//    }
//    int t;
//    for (int i = 0; i < n + m; i++)
//    {
//        for (int j = i; j < m + n; j++)
//        {
//            if (arr[i] > arr[j])
//            {
//                t = arr[i];
//                arr[i] = arr[j];
//                arr[j] = t;
//                
//            }
//        }
//    }
//    for (int i=0; i < m + n; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}


                                             //【一维数组】交换数组
//#include<windows.h>
//#include<stdlib.h>
//int main()
//{
//    char a1[] = { "Welcome to bite!!!" };
//    char a2[] = { "******************" };
//    int right = 0;
//    int left = 17;
//    while (right < left)
//    {
//        a2[right] = a1[right];
//        a2[left] = a1[left];
//        right++;
//        left--;
//        printf("%s\n", a2);
//        Sleep(1000);
//        system("cls");
//    }
//    return 0;
//}


//#include<math.h>
//int main()
//{
//    double a;
//    scanf("%lf", &a);
//    printf("%d", (int)round(a));
//    return 0;
//}



//#include<math.h>
//int main() {
//    unsigned int a;
//    double b, c, d;
//    scanf("%u;%lf,%lf,%lf", &a, &b, &c, &d);
//    printf("The each subject score of No. %u is %.2lf, %.2lf, %.2lf.", a, round(b*100)/100, round(c*100)/100, round(d*100)/100);
//    return 0;
//}



//int main()
//{
//    int a;
//    int b, c, d;
//    scanf("%d", &a);
//    b = a / 10000;
//    c = (a / 100) % 100;
//    d = a % 100;
//    printf("year=%d\nmonth=%02d\ndate=%02d", b, c, d);
//    return 0;
//}



//int main()
//{
//    int a, b;
//    scanf("a=%d,b=%d", &a, &b);
//    printf("a=%d,b=%d", b, a);
//}



//int main() {
//    char n;
//    while (scanf("%c", &n) == 1)
//    {
//        printf("%c", n + 32);
//        getchar();
//    }
//    return 0;
//}


//int main()
//{
//    int a = 0xABCDEF;
//    printf("%15d", a);
//    return 0;
//
//}


//int main()
//{
//    int a = 1234;
//    printf("%#o %#X", a, a);
//    return 0;
//}


//int main()
//{
//    char ch;
//    int i;
//    float k;
//    scanf("%c", &ch);
//    scanf("%d", &i);
//    scanf("%f", &k);
//    printf("%c %d %.6f", ch, i, k);
//    return 0;
//}


//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    printf("%d       %d       %d", a, b, c);
//    return 0;
//}


//#include <stdlib.h>
//int main()
//{
//    int a, b;
//    char c[10], d[10];
//    scanf("%s %s", c, d);
//    a = strtol(c + 2, NULL, 16);
//    b = strtol(d, NULL, 8);
//    printf("%d", a + b);
//    return 0;
//}


//#include <stdio.h>
//
//int main() {
//    int n;
//    double a[100];
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%lf", &a[i]);
//    }
//    double max = a[0], min = a[0], average = a[0];
//    double add = 0;
//    for (int i = 0; i < n; i++)
//    {
//        add += a[i];
//        if (max < a[i])
//        {
//            double t = max;
//            max = a[i];
//            a[i] = max;
//        }
//        if (min > a[i])
//        {
//            double k = min;
//            min = a[i];
//            a[i] = k;
//        }
//        
//    }
//    printf("%.2lf %.2lf %.2lf", max, min, add/n);
//    return 0;
//}



//int main() {
//    double a;
//    scanf("%lf", &a);
//    double b =5.0 / 9 * (a - 32);
//    printf("%.3lf", b);
//    return 0;
//}



//int main() {
//    int h, r;
//    scanf("%d %d", &h, &r);
//    double v = 3.14 * h * r * r ;
//    int a = 10000 / (int)v;
//    if ((10000 % (int)v) != 0)
//        a++;
//    printf("%d", a);
//    return 0;
//}


//BC42 小乐乐定闹钟

//int main()
//{
//    int min, hour;
//    int h;
//    scanf("%d:%d %d", &hour, &min, &h);
//    min += h;
//    while (min >= 60)
//    {
//        min -= 60;
//        hour++;
//    }
//    while (hour >= 24)
//    {
//        if (hour >= 24)
//        {
//            hour -= 24;
//        }
//    }
//    printf("%02d:%02d", hour, min);
//    return 0;
//}



//#include<stdlib.h>
//
//int fn(int a, int b);
//
//int main()
//{
//    int a, b;
//    while (scanf("%d %d", &a, &b) == 2)
//    {
//        int ret = fn(a, b);
//        int k = (a * b) / ret;
//        printf("%d\n", k + ret);
//    }
//    return 0;
//}
//
//int fn(int a, int b)
//{
//    if (a > b)
//    {
//        return fn(a - b, b);
//    }
//    if (a < b)
//    {
//        return fn(a, b - a);
//    }
//    if (a == b)
//    {
//        return a;
//    }
//}



//BC44 小乐乐与欧几里得:
//int main()
//{
//    unsigned int a, b;
//    while (scanf("%u %u", &a, &b) == 2)
//    {
//        unsigned int k = a * b;
//        while (b % a != 0)
//        {
//            unsigned int t = b % a;
//            b = a;
//            a = t;
//        }
//        
//        unsigned int l = k / a;
//        printf("%u", l + a);
//    }
//    return 0;
//}


//BC45 小乐乐改数字
//int main()
//{
//    int a[10] = { 0 };
//    int i = 0;
//    while ((a[i]=getchar()) != '\n')
//    {
//        
//        if (a[i] % 2 == 0)
//        {
//            a[i] = 0;
//        }
//        else
//        {
//            a[i] = 1;
//        }
//        i++;
//    }
//    int t = i;
//    int j = 0;
//    for (int n = 0; n < t; n++)
//    {
//        if (a[n] != 0 && j == 0)
//        {
//            printf("%d", a[n]);
//            j++;
//        }
//         else if (j != 0)
//        {
//            printf("%d", a[n]);
//        }
//    }
//    if (j == 0)
//    {
//        printf("0");
//    }
//    return 0;
//}


//#include <stdio.h>
//
//int main() {
//    char a;
//    while (scanf("%c", &a) == 1)
//    {
//        switch (a)
//    case 'a':
//    case 'A':
//    case 'e':
//    case 'E':
//    case 'i':
//    case 'I':
//    case 'o':
//    case 'O':
//    case 'u':
//    case 'U':
//        printf("Vowel\n");
//        break;
//    default:
//        printf("Consonant\n");
//        break;
//    }
//    return 0;
//}



//BC57 四季
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int b = a % 100;
//    if (b >= 3 && b <= 5)
//        printf("spring\n");
//    if (b >= 6 && b <= 8)
//        printf("summer\n");
//    if (b >= 9 && b <= 11)
//        printf("autumn\n");
//    if (b >= 1 && b <= 2)
//        printf("winter\n");
//    if (b == 12)
//        printf("winter\n");
//    return 0;
//}


//BC58 健康评估
//int main() 
//{
//    double a, b;
//    scanf("%lf %lf", &a, &b);
//    double c = a / (b * b);
//    if (c >= 18.5 && c <= 23.9)
//    {
//        printf("Normal\n");
//    }
//    else
//    {
//        printf("Abnormal\n");
//    }
//    return 0;
//}



//BC59 小乐乐找最大数
//int main()
//{
//    int a[4] = { 0 };
//    for (int i = 0; i < 4; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int max = a[0];
//    for (int i = 0; i < 4; i++)
//    {
//        if (max < a[i])
//        {
//            max = a[i];
//        }
//    }
//    printf("%d", max);
//    return 0;
//}


//BC60 判断是不是字母
//int main()
//{
//    char a;
//    while (scanf("%c", &a) != EOF)
//    {
//        getchar();
//        if ((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z'))
//        {
//            printf("%c is an alphabet.\n", a);
//        }
//        
//        else
//        {
//            printf("%c is not an alphabet.\n", a);
//        }
//    }
//    return 0;
//}


//BC61 牛牛的二三七整除
//int main()
//{
//    int i;
//    scanf("%d", &i);
//    if (i % 2 == 0)
//        printf("2");
//    if (i % 3 == 0)
//        printf("3");
//    if (i % 7 == 0)
//        printf("7");
//    if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0)
//    {
//        printf("n");
//    }
//    return 0;
//}



//BC62 统计数据正负个数
//int main()
//{
//    int a[10] = { 0 };
//    int b = 0, c = 0;
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//        if (a[i] > 0)
//        {
//            b++;
//        }
//        else if (a[i] < 0)
//        {
//            c++;
//        }
//    }
//    printf("positive:%d\nnegative:%d", b, c);
//    
//    return 0;
//}


//BC63 网购
//int main()
//{
//    double a;
//    int month, date, k;
//    scanf("%lf %d %d %d", &a, &month, &date, &k);
//    if ((month == 11) && (date == 11))
//    {
//        if (k == 0)
//            a *= 0.7;
//        else if (k == 1)
//        {
//            a = a * 0.7 - 50;
//        }
//       
//    }
//    else if ((month == 12) && (date == 12))
//    {
//        if (k == 0)
//            a *= 0.8;
//        else if (k == 1)
//        {
//            a = a * 0.8 - 50;
//        }
//    }
//    if (a < 0)
//    {
//        a = 0;
//    }
//    printf("%.2lf", a);
//    return 0;
//}


//BC64 牛牛的快递
//int main()
//{
//    float a;
//    char ch;
//    scanf("%f %c", &a, &ch);
//    int m = 20;
//    while (a > 1)
//    {
//        m += 1;
//        a--;
//    }
//    if (ch == 'y')
//    {
//        m += 5;
//    }
//    printf("%d", m);
//    return 0;
//}


//BC65 计算商品打折结算金额
//int main()
//{
//    double a;
//    scanf("%lf", &a);
//    if (a >= 100 && a < 500)
//    {
//        a *= 0.9;
//    }
//    else if (a >= 500 && a < 2000)
//    {
//        a *= 0.8;
//    }
//    else if (a >= 2000 && a < 5000)
//    {
//        a *= 0.7;
//    }
//    else if (a >= 5000)
//    {
//        a *= 0.6;
//    }
//    printf("%.1lf", a);
//    return 0;
//}


//BC66 牛牛的通勤
//int main()
//{
//    unsigned int a;
//    scanf("%u", &a);
//    int m = 0, n = 0;
//    m = a;
//    n = 10 + a / 10;
//    if (a % 10 != 0)
//    {
//        n++;
//    }
//    if (n > m)
//    {
//        printf("w");
//    }
//    else
//        printf("v");
//    
//    return 0;
//}


//BC67 牛牛的金币
//int main()
//{
//    int x, y, x1, y1;
//    scanf("%d %d", &x, &y);
//    scanf("%d %d", &x1, &y1);
//    int a = x - x1;
//    int b = y - y1;
//
//    if (y1-y==1&&x-x1==0)
//    {
//        printf("u");
//    }
//    else if (y1-y==-1&&x-x1==0)
//    {
//        printf("d");
//    }
//    else if (x1-x==1&&y1-y==0)
//    {
//        printf("r");
//    }
//    else if (x1-x==-1&&y1-y==0)
//    {
//        printf("l");
//    }
//    return 0;
//}


//BC68 牛牛的一周
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    switch (a)
//    {
//    case 1:
//        printf("Monday\n");
//        break;
//    case 2:
//        printf("Tuesday\n");
//        break;
//    case 3:
//        printf("Wednesday\n");
//        break;
//    case 4:
//        printf("Thursday\n");
//        break;
//    case 5:
//        printf("Friday\n");
//        break;
//    case 6:
//        printf("Saturday\n");
//        break;
//    case 7:
//        printf("Sunday\n");
//        break;
//    }
//    return 0;
//}


//BC69 HTTP状态码
//int main()
//{
//    int a;
//    while (scanf("%d", &a) == 1)
//    {
//        switch (a)
//        {
//        case 200:
//            printf("OK\n");
//            break;
//        case 202:
//            printf("Accepted\n");
//            break;
//        case 400:
//            printf("Bad Request\n");
//            break;
//        case 403:
//            printf("Forbidden\n");
//            break;
//        case 404:
//            printf("Not Found\n");
//            break;
//        case 500:
//            printf("Internal Server Error\n");
//            break;
//        case 502:
//            printf("Bad Gateway\n");
//            break;
//        }
//    }
//    return 0;
//}
//200 - OK
//202 - Accepted
//400 - Bad Request
//403 - Forbidden
//404 - Not Found
//500 - Internal Server Error
//502 - Bad Gateway


//BC70 计算单位阶跃函数
//int main()
//{
//    int a;
//    while (scanf("%d", &a) == 1)
//    {
//        if (a > 0)
//        {
//            printf("1\n");
//        }
//        else if (a < 0)
//        {
//            printf("0\n");
//        }
//        else
//        {
//            printf("0.5\n");
//        }
//    }
//    return 0;
//}


//BC72 牛牛的计划
//int main()
//{
//    int y, m, d, a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    scanf("%d %d %d", &y, &m, &d);
//    if (y > a)
//    {
//        printf("yes\n");
//    }
//    else if(y < a)
//    {
//        printf("no\n");
//    }
//    else
//    {
//        if (m > b)
//        {
//            printf("yes\n");
//        }
//        else if (m < b)
//        {
//            printf("no");
//        }
//        else
//        {
//            if (d >= c)
//            {
//                printf("yes");
//            }
//            else
//            {
//                printf("no");
//            }
//        }
//
//    }
//    return 0;
//}


//BC73 计算一元二次方程
//#include<math.h>
//int main()
//{
//    double a, b, c;
//    while (scanf("%lf %lf %lf", &a, &b, &c) == 3)
//    {
//         double p = -b;
//        if (a == 0)
//        {
//            printf("Not quadratic equation\n");
//            continue;
//        }
//        else
//        {
//            double t = b * b - 4 * a * c;
//            double x1 = (p - sqrt(t)) / (2 * a);
//            double x2 = (p + sqrt(t)) / (2 * a);
//            if (x1 == -0.00)
//            {
//                x1 = 0.00;
//            }
//            if (x2 == -0.00)
//            {
//                x2 = 0.00;
//            }
//            if (t > 0)
//            {
//                printf("x1=%.2lf;x2=%.2lf\n", x1, x2);
//            }
//            else if (t == 0)
//            {
//                printf("x1=x2=%.2lf\n", x1);
//            }
//            else
//            {
//                double m, n;
//                m = p / (2 * a);
//                n = sqrt(-t) / (2 * a);
//                if (m == -0.00)
//                {
//                    m = 0.00;
//                }
//                if(a>0)
//                printf("x1=%.2lf-%.2lfi;x2=%.2lf+%.2lfi\n", m, n, m, n);
//                else
//                printf("x1=%.2lf+%.2lfi;x2=%.2lf-%.2lfi\n", m, n, m, n);
//            }
//            
//        }
//    }
//    return 0;
//}



//BC74 获得月份天数
//int fn(int a,int b);
//int ln(int u);
//int main()
//{
//    int a, b;
//    while (scanf("%d %d", &a, &b) != EOF)
//    {
//        int k = fn(a, b);
//        printf("%d\n", k);
//    }
//    return 0;
//}
//
//int fn(int a,int b)
//{
//    int l[14] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//    if (ln(a))
//        l[2] = 29;
//    int y = l[b];
//    return y;
//}
//
//int ln(int u)
//{
//    if ((u % 4 == 0 && u % 100 != 0) || u % 400 == 0)
//    {
//        return 1;
//    }
//    else
//        return 0;
//}


//BC75 小乐乐是否被叫家长
//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    int i = (a + b + c) / 3;
//    if (i >= 60)
//    {
//        printf("NO\n");
//    }
//    else
//        printf("YES\n");
//    return 0;
//}


//BC76 [NOIP2008]ISBN号码
//int main()
//{
//    char a[13];
//    char b[13];
//    int k = 0;
//    for (int i = 0; i < 13; i++)
//    {
//        scanf("%c", &a[i]);
//        if (i == 1 || i == 5 || i == 11||i == 12)
//        {
//            ;
//        }
//        else
//        {
//            b[k] = a[i];
//            k++;
//        }
//
//    }
//    int add = 0;
//    int h = 1;
//    for (int i = 0; i < 9; i++)
//    {
//        int m = b[i] - '0';
//        add += h * m;
//        h++;
//    }
//    int n = add % 11;
//    char ch;
//    if (n==10)
//    {
//        ch = 'X';
//    }
//    else
//    {
//        ch = n + '0';
//    }
//    if (ch == a[12])
//    {
//        printf("Right\n");
//    }
//    else
//    {
//        a[12] = ch;
//        for (int i = 0; i < 13; i++)
//        {
//            printf("%c", a[i]);
//        }
//    }
//    return 0;
//}


//BC77 简单计算器
//int main()
//{
//    double a, b;
//    char c;
//    scanf("%lf%c%lf", &a, &c, &b);
//    double k;
//    switch (c)
//    {
//    case '+':
//    
//        k = a + b;
//        printf("%.4lf+%.4lf=%.4lf", a, b, k);
//        break;
//    case '-':
//        k = a - b;
//        printf("%.4lf-%.4lf=%.4lf", a, b, k);
//        break;
//    case '*':
//        k = a * b;
//        printf("%.4lf*%.4lf=%.4lf", a, b, k);
//        break;
//    case '/':
//        if (b == 0)
//        {
//            printf("Wrong!Division by zero!\n");
//            break;
//        }
//        k = a / b;
//        printf("%.4lf/%.4lf=%.4lf", a, b, k);
//        break;
//    default:
//        printf("Invalid operation!\n");
//        break;
//    }
//    return 0;
//}



//二分查找函数
//int fn(int a[], int right, int left, int key);
//
//int main()
//{
//    int a[10] = { 0,1,2,3,4,5,6,7,8,12 };
//    int right, left, key;
//    while (scanf("%d", &key) != EOF)
//    {
//        right = sizeof(a) / sizeof(a[0]);
//        left = 0;
//        int i = fn(a, right, left, key);
//
//        if (i == -1)
//        {
//            printf("没有找到该数字！！！\n");
//        }
//        else
//        {
//            printf("找到了，它的下标是%d.\n", i);
//        }
//    }
//    return 0;
//}
//
//int fn(int a[10], int right, int left, int key)
//{
//    int mid;
//    int l = -1;
//    while (right>=left)
//    {
//        mid = (right + left) / 2;
//        if (key > a[mid])
//        {
//            left = mid + 1;
//        }
//        if (key < a[mid])
//        {
//            right = mid - 1;
//        }
//        if (key == a[mid])
//        {
//            l = mid;
//            break;
//        }
//    }
//        return l;
//}



//乘法口诀表
//void fn(int n);
//
//int main()
//{
//    int n;
//    while (scanf("%d", &n) != EOF)
//    {
//        fn(n);
//    }
//    return 0;
//}
//
//void fn(int n)
//{
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = i; j <= n; j++)
//        {
//            printf("%2d*%2d=%2d  ", i, j, i * j);
//        }
//        printf("\n");
//    }
//}



//函数判断闰年
//int fn(int n);
//
//int main()
//{
//    int n;
//    while (scanf("%d", &n) != EOF)
//    {
//        int i = fn(n);
//        if (i)
//        {
//            printf("Yes\n");
//        }
//        else
//        {
//            printf("No\n");
//        }
//    }
//    return 0;
//}
//
//int fn(int n)
//{
//    if ((n % 4 == 0 && n % 100 != 0) || n % 400 == 0)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}



//函数判断素数
//#include<math.h>
//int fn(int i);
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int i;
//    for (i = m; i <= n; i++)
//    {
//        int k = fn(i);
//        if (k == 1)
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}
//
//int fn(int i)
//{
//    int j;
//    for (j = 2; j <= sqrt(i); j++)
//    {
//        if (i % j == 0)
//        {
//            break;
//        }
//    }
//    if (j > sqrt(i))
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}



//void fn(int a[],int n);
//int main()
//{
//    int a[100];
//    int n;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    fn(a,n);
//    for (int i = 0; i < n; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    return 0;
//}
//
//void fn(int a[],int n)
//{
//    int i, j;
//    for (i = n-1,j = 0;j<i; i--,j++)
//    {
//        int t = a[i];
//        a[i] = a[j];
//        a[j] = t;
//    }
//}


//BC78 KiKi说祝福语
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        printf("Happy new year!Good luck!\n");
//    }
//    return 0;
//}


//BC79 小乐乐求和
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    long long int add = 0;
//    for (int i = n; i >= 0; i--)
//    {
//        add += i;
//    }
//    printf("%lld", add);
//    return 0;
//}


//BC80 奇偶统计
//int main()
//{
//    int jishu = 0;
//    int oushu = 0;
//    int a;
//    scanf("%d", &a);
//    for (int i = 1; i <= a; i++)
//    {
//        if (i % 2 == 0)
//        {
//            oushu++;
//        }
//        else
//        {
//            jishu++;
//        }
//    }
//    printf("%d %d", jishu, oushu);
//    return 0;
//}



//BC81 KiKi求质数个数
//#include<math.h>
//int fn(int i);
//int main()
//{
//    int count = 0;
//    for (int i = 100; i < 999; i++)
//    {
//        if (fn(i))
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}
//
//int fn(int i)
//{
//    int j;
//    for (j = 2; j <= sqrt(i); j++)
//    {
//        if (i % j == 0)
//        {
//            break;
//        }
//    }
//    if (j > sqrt(i))
//    {
//        return 1;
//    }
//    else
//        return 0;
//}


//BC82 乘法表
//int main()
//{
//    for (int i = 1; i <= 9; i++)
//    {
//        for (int j = 1; j <= i; j++)
//        {
//            printf("%d*%d=%2d ", j, i, j * i);
//        }
//        printf("\n");
//    }
//    return 0;
//}


//BC83 牛牛学数列
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int d = -1;
//    int k = 0;
//    int l = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        d *= -1;
//        k = i * d;
//        l += k;
//    }
//    printf("%d", l);
//    return 0;
//}

//
//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include <stdio.h>
//#include <time.h>
//
//int main() {
//    clock_t start_time, end_time;
//    double cpu_time_used;
//
//    start_time = clock(); // 记录开始时间
//
//    int a;
//    scanf("%d", &a);
//    // 这里可以放需要计时的代码段
//
//    end_time = clock(); // 记录结束时间
//
//    cpu_time_used = ((double)(end_time - start_time)) / CLOCKS_PER_SEC; // 计算所用的CPU时间
//
//    printf("执行时间：%f 秒\n", cpu_time_used);
//
//    return 0;
//}


//7-25 判断上三角矩阵
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        int l;
//        scanf("%d", &l);
//        int t[10][10] = { 0 };
//        int a = 0;
//        for (int j = 0; j < l; j++)
//        {
//            for (int k = 0; k < l; k++)
//            {
//                scanf("%d", &t[j][k]);
//            }
//        }
//        for (int j = 1; j < l; j++)
//        {
//            for (int k = 0; k < j; k++)
//            {
//                if (t[j][k] != 0)
//                {
//                    a++;
//                }
//                else
//                    a = a;
//            }
//        }
//        if (a)
//        {
//            printf("NO\n");
//        }
//        else if (!a)
//            printf("YES\n");
//    }
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    char a[200];
//    fgets(a,sizeof(a),stdin);
//    char k;
//    scanf("%c", &k);
//    int sz = sizeof(a) / sizeof(a[0]);
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[i] == k)
//        {
//            for (int j = i; j < sz; j++)
//            {
//                a[j] = a[j + 1];
//                i--;
//            }
//        }
//    }
//    printf("%s", a);
//    return 0;
//}



//#include <stdio.h>
//
//void sum_diff(float op1, float op2, float* psum, float* pdiff);
//
//int main()
//{
//    float a, b, sum, diff;
//
//    scanf("%f %f", &a, &b);
//    sum_diff(a, b, &sum, &diff);
//    printf("The sum is %.2f\nThe diff is %.2f\n", sum, diff);
//
//    return 0;
//}
//
//void sum_diff(float op1, float op2, float* psum, float* pdiff)
//{
//    (*psum) = op1 + op2;
//    (*pdiff) = op1 - op2;
//}



//#include <stdio.h>
//
//void findmax(int* px, int* py, int* pmax);
//
//int main()
//{
//    int max, x, y;
//
//    scanf("%d %d", &x, &y);
//    findmax(&x, &y, &max);
//    printf("%d\n", max);
//
//    return 0;
//}
//
//void findmax(int* px, int* py, int* pmax)
//{
//    *pmax = (*px > *py ? *px : *py);
//}

//
//#include <stdio.h>
//#define MAXN 10
//
//int search(int list[], int n, int x);
//
//int main()
//{
//
//    int i, index, n, x;
//    int a[MAXN];
//
//    scanf("%d", &n);
//    for (i = 0; i < n; i++)
//        scanf("%d", &a[i]);
//    scanf("%d", &x);
//    index = search(a, n, x);
//    if (index != -1)
//        printf("index = %d\n", index);
//    else
//        printf("Not found\n");
//    return 0;
//
//}
//
//
//int search(int list[], int n, int x)
//{
//    int i = 0;
//    for ( i = 0; i < n; i++)
//    {
//        if (list[i] == x)
//        {
//            return i;
//            break;
//        }
//    }
//    return -1;
//}


//#include <stdio.h>
//#define MAXN 10
//
//void sort(int a[], int n);
//
//int main()
//{
//    int i, n;
//    int a[MAXN];
//
//    scanf("%d", &n);
//    for (i = 0; i < n; i++)
//        scanf("%d", &a[i]);
//
//    sort(a, n);
//
//    printf("After sorted the array is:");
//    for (i = 0; i < n; i++)
//        printf(" %d", a[i]);
//    printf("\n");
//
//    return 0;
//}
//
//void sort(int a[], int n)
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = i; j < n; j++)
//        {
//            if (a[i] > a[j])
//            {
//                int t = a[i];
//                a[i] = a[j];
//                a[j] = t;
//            }
//        }
//    }
//}


//#include <stdio.h>
//#define MAXN 10
//
//void ArrayShift(int a[], int n, int m);
//
//int main()
//{
//    int a[MAXN], n, m;
//    int i;
//
//    scanf("%d %d", &n, &m);
//    for (i = 0; i < n; i++) scanf("%d", &a[i]);
//
//    ArrayShift(a, n, m);
//
//    for (i = 0; i < n; i++) {
//        if (i != 0) printf(" ");
//        printf("%d", a[i]);
//    }
//    printf("\n");
//
//    return 0;
//}
//
//void ArrayShift(int a[], int n, int m)
//{
//    int b[m];
//}

//
//#include <stdio.h>
//#define MAXN 20
//
//void strmcpy(char* t, int m, char* s);
//void ReadString(char s[]); /* 由裁判实现，略去不表 */
//
//int main()
//{
//    char t[MAXN], s[MAXN];
//    int m;
//
//    scanf("%d\n", &m);
//    ReadString(t);
//    strmcpy(t, m, s);
//    printf("%s\n", s);
//
//    return 0;
//}
//
//void strmcpy(char* t, int m, char* s)
//{
//
//}



//#include <stdio.h>
//#include <string.h>
//
//#define MAXS 10
//
//char* str_cat(char* s, char* t);
//
//int main()
//{
//    char* p;
//    char str1[MAXS + MAXS] = { '\0' }, str2[MAXS] = { '\0' };
//
//    scanf("%s%s", str1, str2);
//    p = str_cat(str1, str2);
//    printf("%s\n%s\n", p, str1);
//
//    return 0;
//}
//
//char* str_cat(char* s, char* t)
//{
//    strcat(s, t);
//    return s;
//}



//#include <stdio.h>
//void fun(char* s);
//int main()
//{
//    char a[80], * s;
//    s = a;
//    gets(s);
//    fun(s);
//    printf("the result: %s\n", s);
//    return 0;
//}
//
//void fun(char* s)
//{
//    int i = 0;
//    while (s[i] != '\0')
//    {
//        if (s[i] >= '0' && s[i] <= '9')
//        {
//            s[i] = '#';
//        }
//        i++;
//    }
//}



//#include <stdio.h>
//char* match(char* s, char ch);      /* 函数声明 */
//int main(void)
//{
//    char ch, str[80], * p = NULL;
//
//    scanf("%s", str);
//    getchar();
//    ch = getchar();
//    if ((p = match(str, ch)) != NULL)
//        printf("%s\n", p);
//    else
//        printf("Not Found\n");
//    return 0;
//}
//
//
//char* match(char* s, char ch)
//{
//    int i = 0;
//    int j = 0;
//    while (s[i] != ch&&s[i]!='\0')
//    {
//        i++;
//    }
//    if (s[i] = '\0')
//    {
//        return;
//    }
//    while (s[i] != '\0')
//    {
//        s[j] = s[i];
//        i++;
//        j++;
//    }
//    s[j] = '\0';
//}



//#include <stdio.h>
//double getScore(int* score, int total);
//int main() {
//    int i, score[20], N;
//    scanf("%d\n", &N);
//    for (i = 0; i < N; i++)
//        scanf("%d", &score[i]);
//    printf("%.2f\n", getScore(score, N));  /* getScore( )函数只负责返回分值，由main函数中的代码负责按照2位小数打印输出 */
//    return 0;
//}
//
//double getScore(int* score, int total)
//{
//    int max, min;
//    max = score[0];
//    min = score[0];
//    for (int i = 0; i < total; i++)
//    {
//        if (max < score[i])
//        {
//            max = score[i];
//        }
//        if (min > score[i])
//        {
//            min = score[i];
//        }
//    }
//    double add=0;
//    for (int i = 0; i < total; i++)
//    {
//        if (score[i] != max && score[i] != min)
//        {
//            add += score[i];
//        }
//    }
//    return add / (total - 2);
//}



//#include<stdio.h>
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    double l[10000];
//    double add = 0;
//    for (int i = 0; i < a; i++)
//    {
//        scanf("%lf", &l[i]);
//        add += l[i];
//    }
//    double max, min;
//    max = l[0];
//    min = l[0];
//    for (int i = 0; i < a; i++)
//    {
//        if (max < l[i])
//        {
//            max = l[i];
//        }
//        if (min > l[i])
//        {
//            min = l[i];
//        }
//    }
//    if (a == 1)
//    {
//        max = l[0];
//        min = l[0];
//        add = l[0];
//    }
//    printf("average = %.2lf\nmax = %.2lf\nmin = %.2lf", add / a, max, min);
//    return 0;
//}




//#include <stdio.h>
//
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int l[200][200];
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            scanf("%d", &l[i][j]);
//        }
//    }
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            for (int n = 0; n < b - j - 1; n++)
//            {
//                if (l[i][n] > l[i][n + 1])
//                {
//                    int t = l[i][n];
//                    l[i][n] = l[i][n + 1];
//                    l[i][n + 1] = t;
//                }
//            }
//        }
//    }
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            printf("%d ", l[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}


//#include<string.h>
//int main()
//{
//    char a[200];
//    scanf("%s", a);
//    int k = strlen(a);
//    printf("%d", k);
//    return 0;
//}



//#include <stdio.h>
//#include <string.h>
//
//void DNApaixu(char* str);
//
//int main()
//{
//    int N, i;
//    char a[500];
//    scanf("%d", &N);
//    for (i = 0; i < N; i++)
//    {
//        scanf("%s", a);
//        DNApaixu(a);
//        printf("\n");
//    }
//
//    return 0;
//
//}
//
//void DNApaixu(char* str)
//{
//    int n, i, j;
//    n = strlen(str);
//    printf("%s ", str);
//    for (i = 1; i < n; i++)
//    {
//        str[n] = str[0];
//        for (j = 1; j <= n; j++)
//        {
//            str[j - 1] = str[j];
//        }
//        str[j - 1] = '\0';
//        printf("%s ", str);
//    }
//}



//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    char a[90];
//    char b[90];
//    scanf("%s", a);
//    for (int i = 1; i < n; i++)
//    {
//        scanf("%s", b);
//        int p = strcmp(a, b);
//        if (p > 0)
//        {
//            strcpy(a, b);
//        }
//
//    }
//    printf("Min is: %s", a);
//    return 0;
//}



//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    char p[5][80];
//    for (int i = 0; i < 5; i++)
//    {
//        scanf("%s", p[i]);
//    }
//    for (int i = 0; i < 4; i++)
//    {
//        for (int j = 0; j < 5 - i; j++)
//        {
//            if (strcmp(p[j], p[j + 1]) > 0)
//            {
//                char o[90];
//                strcpy(o, p[j]);
//                strcpy(p[j], p[j + 1]);
//                strcpy(p[j + 1], o);
//            }
//        }
//    }
//    printf("After sorted:\n");
//    for (int i = 0; i < 5; i++)
//    {
//        printf("%s\n", p[i]);
//    }
//    return 0;
//}



//#include<stdio.h>
//#include<string.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    double a[20][20];
//    double b[20];
//    double add = 0.00000;
//    double q[20];
//    int s[20];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%lf", &a[i][j]);
//        }
//    }
//    double max, min;
//    for (int i = 0; i < m; i++)
//    {
//        s[i] = i + 1;
//    }
//    for (int i = 0; i < m; i++)
//    {
//        add = 0;
//        max = a[i][0];
//        min = a[i][0];
//        for (int j = 0; j < n; j++)
//        {
//            if (max < a[i][j])
//            {
//                max = a[i][j];
//            }
//            if (min > a[i][j])
//            {
//                min = a[i][j];
//            }
//            add += a[i][j];
//        }
//        b[i] = (add - max - min) / n;
//    }
//    for (int i = 0; i < m; i++)
//    {
//        q[i] = b[i];
//    }
//    for (int i = 0; i < m; i++)
//    {
//        for (int l = 0; l < m - i; l++)
//        {
//            if (q[l] < q[l + 1])
//            {
//                double v = q[l];
//                q[l] = q[l + 1];
//                q[l + 1] = v;
//                int u = s[l];
//                s[l] = s[l + 1];
//                s[l + 1] = u;
//            }
//        }
//    }
//    for (int i = 0; i < m; i++)
//    {
//        printf("%3d", s[i]);
//   }
//    return 0;
//}


//int main()
//{
//    char a[2000] = { 0 };
//    fgets(a, sizeof(a), stdin);
//    int sz = sizeof(a) / sizeof(a[0]);
//    int h = 0;
//    int b[2000] = { 0 };
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[i] >= 'a' && a[i] <= 'z')
//        {
//            a[i] -= 32;
//            b[i] = 1;
//            break;
//        }
//        if (a[i] >= 'A' && a[i] < 'Z')
//        {
//            b[i] = 1;
//            break;
//        }
//    }
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[i] >= 'A' && a[i] <= 'Z' && b[i] == 0)
//        {
//            a[i] += 32;
//        }
//    }
//    printf("%s", a);
//    return 0;
//}


//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int m;
//    int a[20][20] = { 0 };
//    int p = 0;
//    int q = 0;
//    int v = 0;
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &m);
//        p = 0;
//        q = 0;
//        v = 0;
//        for (int j = 0; j < m; j++)
//        {
//            for (int h = 0; h < m; h++)
//            {
//                scanf("%d", &a[j][h]);
//            }
//        }
//        for (int j = 0; j < m; j++)
//        {
//            for (int h = 0; h < j; h++)
//            {
//                if (a[j][h] != 0)
//                {
//                    p++;
//                    break;
//                }
//            }
//           
//            for (int h = j + 1; h < m; h++)
//            {
//                if (a[j][h] != 0)
//                {
//                    q++;
//                    break;
//                }
//            }
//        }
//        if (p == 0)
//        {
//            printf("upper triangular matrix\n");
//        }
//        else if (q == 0)
//        {
//            printf("lower triangular matrix\n");
//        }
//        else
//        {
//            printf("no\n");
//        }
//    }
//    
//    return 0;
//}



//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int m;
//    int a[100][100] = { 0 };
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &m);
//        int q = 0;
//        int w = 0; 
//        int e = 0;
//        for (int x = 0; x < m; x++)
//        {
//           for (int y = 0; y < m; y++)
//            {
//                scanf("%d", &a[x][y]);
//            }
//        }
//        for (int x = 0; x < m; x++)
//        {
//            for (int y = 0; y < x; y++)
//            {
//                if (a[x][y] != 0)
//                {
//                    q = 1;
//                    break;
//                }
//            }
//            if (q == 1)
//            {
//                break;
//            }
//        }
//        for (int x = 0; x < m; x++)
//        {
//            for (int y = x + 1; y < m; y++)
//            {
//                if (a[x][y] != 0)
//                {
//                    w = 1;
//                    break;
//                }
//            }
//            if (w == 1)
//            {
//                break;
//            }
//        }
//        if (q == 0)
//        {
//            printf("upper triangular matrix\n");
//        }
//        else if (w == 0)
//        {
//            printf("lower triangular matrix\n");
//        }
//        else
//        {
//            printf("no\n");
//        }
//    }
//    return 0;
//}



//#include <stdio.h>
//#include <math.h>
//
//int prime(int p);
//int PrimeSum(int m, int n);
//
//int main()
//{
//    int m, n, p;
//
//    scanf("%d %d", &m, &n);
//    printf("Sum of ( ");
//    for (p = m; p <= n; p++) {
//        if (prime(p) != 0)
//            printf("%d ", p);
//    }
//    printf(") = %d\n", PrimeSum(m, n));
//
//    return 0;
//}

//int prime(int p)
//{
//    int i;
//    if (p > 1)
//    {
//        for (i = 2; i <= sqrt(p); i++)
//        {
//            if (p % i == 0)
//            {
//                break;
//            }
//        }
//        if (i > sqrt(p))
//        {
//            return 1;
//        }
//        else
//        {
//            return 0;
//        }
//    }
//    else
//        return 0;
//}
//int PrimeSum(int m, int n)
//{
//    int add = 0;
//    for (int i = m; i <= n; i++)
//    {
//        if (prime(i)==1)
//        {
//            add += i;
//        }
//    }
//    return add;
//}


//#include<stdio.h>
//#include<math.h>
//int prime(int p);
//
//int main()
//{
//    int cnt, m, n, p;
//    cnt = 0;
//    scanf("%d %d", &m, &n);
//    printf("Count of ( ");
//    for (p = m; p <= n; p++) {
//        if (prime(p) == 1) {
//            printf("%d ", p);
//            cnt++;
//        }
//    }
//    printf(") = %d\n", cnt);
//    return 0;
//}
//
//
//int prime(int p)
//{
//    int i;
//    for (i = 2; i <= sqrt(p); i++)
//    {
//        if (p % i == 0)
//        {
//            break;
//        }
//    }
//    if (i > sqrt(p) &&p != 1)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}



//#include <stdio.h>
//#define N 1000
//
//int  prime(int x);
//
//
//int main()
//{
//    int x, k;
//    scanf("%d", &x);
//    k = prime(x);
//    if (k)
//        printf("%d is prime", x);
//    else
//        printf("%d is not prime", x);
//    return 0;
//}
//
//int  prime(int x)
//{
//    if (x > 1)
//    {
//        int i;
//        for (i = 2; i <= sqrt(x); i++)
//        {
//            if (x % i == 0)
//            {
//                break;
//            }
//        }
//        if (i > sqrt(x))
//        {
//            return 1;
//        }
//        else
//        {
//            return 0;
//        }
//    }
//    else
//    {
//        return 0;
//    }
//}



//#include <stdio.h>
//
//int fib(int n);
//void PrintFN(int m, int n);
//
//int main()
//{
//    int m, n, t;
//
//    scanf("%d %d %d", &m, &n, &t);
//    printf("fib(%d) = %d\n", t, fib(t));
//    PrintFN(m, n);
//
//    return 0;
//}

//int fib(int n)
//{
//    int a[110];
//    a[0] = 0;
//    a[1] = 1;
//    for (int i = 2; i <= n; i++)
//    {
//        a[i] = a[i - 1] + a[i - 2];
//    }
//    return a[n];
//}
//void PrintFN(int m, int n)
//{
//    int a[11000];
//    int b = 0;
//    for (int i = 0; i <= 10000; i++)
//    {
//        if (i == 1 || i == 0)
//        {
//            a[i] = 1;
//        }
//        else
//        {
//            a[i] = a[i - 1] + a[i - 2];
//        }
//        if (a[i] >= m && a[i] <= n && b == 0)
//        {
//            printf("%d", a[i]);
//            b++;
//        }
//        else if (a[i] >= m && a[i] <= n && b != 0)
//        {
//            printf(" %d", a[i]);
//        }
//    }
//    if (!b)
//    {
//        printf("No Fibonacci number\n");
//    }
//}



//#include <stdio.h>
//
//int fib(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    printf("%d\n", fib(n));
//
//    return 0;
//}
//
//int fib(int n)
//{
//    int a[10000];
//    a[0] = 0;
//    a[1] = 1;
//    for (int i = 2; i < 10000; i++)
//    {
//        a[i] = a[i - 1] + a[i - 2];
//        if (i == n)
//        {
//            break;
//        }
//    }
//    return a[n];
//}



//#include <stdio.h>
//
//int IsDigit(char x);
//
//int main()
//{
//    char c;
//    c = getchar();
//    if (IsDigit(c))
//    {
//        putchar('Y');
//    }
//    else
//    {
//        putchar('N');
//    }
//    putchar('\n');
//    return 0;
//}
//
//int IsDigit(char x)
//{
//    if (x >= 48 && x <= 57)
//    {
//        return 1;
//    }
//    else
//        return 0;
//}





//#include <stdio.h>
//
//int isPerfect(int x);
//
//int main()
//{
//    for (int i = 1; i <= 10000; i++)
//    {
//        if (isPerfect(i))
//        {
//            printf("%d\n", i);
//        }
//    }
//    return 0;
//}
//
//int isPerfect(int x)
//{
//    int add = 0;
//    for (int i = 1; i < x; i++)
//    {
//        if (x % i == 0)
//        {
//            add += i;
//        }
//    }
//    if (x == add)
//    {
//        return 1;
//    }
//    else
//        return 0;
//}



//#include <stdio.h>
//
//int f(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    printf("%d\n", f(n));
//
//    return 0;
//}
//int f(int n)
//{
//    if (n <= 0)
//    {
//        return 0;
//    }
//    else if (n == 1)
//    {
//        return 1;
//    }
//    else
//    {
//        return f(n - 1) + f(n - 2);
//    }
//}



//#include <stdio.h>
//
//double Fac(int x);
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    printf("%.10g\n", Fac(n));
//    return 0;
//}
//
//double Fac(int x)
//{
//    if (x == 0)
//    {
//        return 1;
//    }
//    else if (x == 1)
//    {
//        return 1;
//    }
//    else
//    {
//        return x * Fac(x - 1);
//    }
//}



//#include <stdio.h>
//
//int TotalLeapYear(int year);
//
//int main()
//{
//    int y;
//    scanf("%d", &y);
//    printf("%d\n", TotalLeapYear(y));
//    return 0;
//}
//
//
//int TotalLeapYear(int year)
//{
//        int a = 0;
//        for (int i = 4; i <= year; i++)
//        {
//            if ((i % 4 == 0 && i % 100 != 0) || (i % 400 == 0))
//            {
//                a++;
//            }
//        }
//        return a;
//}



//#include <stdio.h>
//#define MAXN 20
//
//void strmcpy(char* t, int m, char* s);
//void ReadString(char s[]); /* 由裁判实现，略去不表 */
//
//int main()
//{
//    char t[MAXN], s[MAXN];
//    int m;
//
//    scanf("%d\n", &m);
//    ReadString(t);
//    strmcpy(t, m, s);
//    printf("%s\n", s);
//
//    return 0;
//}
//#include<string.h>
//void strmcpy(char* t, int m, char* s)
//{
//    int sz = strlen(t);
//    for (int i = m; i < sz; i++)
//    {
//        s[i - m] = t[i];
//    }
//    s[sz - m] = '\0';
//}



//#include <stdio.h>
//#include <string.h>
//
//#define MAXN 20
//typedef enum { false, true } bool;
//bool palindrome(char* s);
//
//int main()
//{
//    char s[MAXN];
//
//    scanf("%s", s);
//    if (palindrome(s) == true)
//        printf("Yes\n");
//    else
//        printf("No\n");
//    printf("%s\n", s);
//
//    return 0;
//}
//
//bool palindrome(char* s)
//{
//    int sz = strlen(s);
//    int i = 0;
//    for ( i = 0; i < sz; i++)
//    {
//        if (s[i] != s[sz - i - 1])
//        {
//            break;
//        } 
//    }
//    if (i == sz)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}



//#include <stdio.h>
//#include <string.h>
//
//#define MAXS 10
//
//char* str_cat(char* s, char* t);
//
//int main()
//{
//    char* p;
//    char str1[MAXS + MAXS] = { '\0' }, str2[MAXS] = { '\0' };
//
//    scanf("%s%s", str1, str2);
//    p = str_cat(str1, str2);
//    printf("%s\n%s\n", p, str1);
//
//    return 0;
//}
//
//char* str_cat(char* s, char* t)
//{
//    int i;
//    int sz = strlen(s);
//    int sz1 = strlen(t);
//    int a = 0;
//    for (i = sz; a<sz1 ; i++)
//    {
//        s[i] = t[a];
//        a++;
//    }
//    //s[i] = '\0';
//    return s;
//}



//#include <stdio.h>
//#define N 5
//float Fun(int* p, int n, int* max);
//
//int main()
//{
//    int a[10], i, max;
//    int* pa = a;
//    float ave;
//    for (i = 0; i < N; i++)
//        scanf("%d", &a[i]);
//    ave = Fun(pa, N, &max);
//    printf("max=%d,average=%.2f", max, ave);
//    return 0;
//}
//
//float Fun(int* p, int n, int* max)
//{
//    *max = *p;
//    float add = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (*max < *p)
//        {
//            *max = *p;
//        }
//        add += *p;
//        p++;
//    }
//    return add / n;
//}



//#include <stdio.h>
//
//void fun(int x, int y, int* p, int* q, float* s);
//int main()
//{
//    int x, y, sum, product; float aver;
//    scanf("%d%d", &x, &y);
//    fun(x, y, &sum, &product, &aver);
//    printf("%d,%d,%.1f", sum, product, aver);
//    return 0;
//}
//
//void fun(int x, int y, int* p, int* q, float* s)
//{
//    *p = x + y;
//    *q = x * y;
//    *s = *p / (float)2;
//}




//#include "stdio.h"
//#define SIZE 5    
//
//int fun(int list[], int size);
//
//int main()
//{
//    int i, v[SIZE];
//    for (i = 0; i < SIZE; i++)
//    {
//        scanf("%d", v + i);
//    }
//    i = fun(v, SIZE);
//    printf("index=%d, min=%d", i, v[i]);
//    return 0;
//}
//
//int fun(int list[], int size)
//{
//    int min = list[0];
//    int a;
//    for (int i = 0; i < size; i++)
//    {
//        if (min > list[i])
//        {
//            min = list[i];
//            a = i;
//        }
//    }
//    return a;
//}




//#include <stdio.h>
//#define MAXS 15
//
//void StringCount(char s[]);
//void ReadString(char s[]); /* 由裁判实现，略去不表 */
//
//int main()
//{
//    char s[MAXS];
//
//    ReadString(s);
//    StringCount(s);
//
//    return 0;
//}
//#include<string.h>
//void StringCount(char s[])
//{
//    int a = 0, b = 0, c = 0, d = 0;
//    int sz = strlen(s);
//    for (int i = 0; i < sz; i++)
//    {
//        if (s[i] >= 'a' && s[i] <= 'z')
//        {
//            a++;
//        }
//        else if (s[i] >= 'A' && s[i] <= 'Z')
//        {
//            a++;
//        }
//        else if (s[i] == '\n' || s[i] == ' ')
//        {
//            b++;
//        }
//        else if (s[i] >= '0' && s[i] <= '9')
//        {
//            c++;
//        }
//        else
//        {
//            d++;
//        }
//    }
//    printf("letter = %d, blank = %d, digit = %d, other = %d", a, b, c, d);
//}




//在这里给出函数被调用进行测试的例子。例如：
//#include <stdio.h>
//int fun(char str1[], char str2[]);
//int main()
//{
//
//    char str1[20], str2[20];
//    scanf("%s", str1);
//    scanf("%s", str2);
//    printf("%d", fun(str1, str2));
//}
//#include<string.h>
//int fun(char str1[], char str2[])
//{
//    int a = 0;
//    int sz1 = strlen(str1);
//    int sz2 = strlen(str2);
//    for (int i = 0; i < sz1; i++)
//    {
//        for (int j = 0; j < sz2; j++)
//        {
//            if (str1[i] == str2[j])
//            {
//                a++;
//            }
//        }
//    }
//    return a;
//}




//#define M 5
//#define N 4
//#include "stdio.h"
//int fun(int a[M][N]);
//int main()
//{
//    int a[M][N], i, j;
//    int y;
//    for (i = 0; i < M; i++)
//        for (j = 0; j < N; j++)
//            scanf("%d", &a[i][j]);
//    y = fun(a);
//    printf("s=%d", y);
//    return 0;
//}
//
//
//int fun(int a[M][N])
//{
//    int add = 0;
//    for (int i = 0; i < M; i++)
//    {
//        for (int j = 0; j < N; j++)
//        {
//            if (i == 0)
//            {
//                add += a[i][j];
//            }
//            else if (j == 0)
//            {
//                add += a[i][j];
//            }
//            else if(i == M - 1)
//            {
//                add += a[i][j];
//            }
//            else if (j == N - 1)
//            {
//                add += a[i][j];
//            }
//        }
//    }
//    return add;
//}



//#include<stdio.h>
//#define N 10
//void createMatrix(int(*a)[N], int n)
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//}
//
//int sumMatrix(int a[N][N])
//{
//    int add = 0;
//    for (int i = 0; i < N; i++)
//    {
//        int j;
//        for ( j = 0; j < N; j++)
//        {
//            if (i != j && i + j != N - 1)
//            {
//                add += a[i][j];
//            }
//        }
//    }
//    return add;
//}
//int main()
//{
//    int a[N][N];
//    createMatrix(a,N);
//    printf("%d\n", sumMatrix(a));
//    return 0;
//}



//int main()
//{
//    int n;
//    double add = 0;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//    {
//        add += 1.0 / i;
//    }
//    printf("%lf", add);
//    return 0;
//}


//#include<math.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    double add = 0;
//    double a = 0;
//    double b = 1;
//    for (int i = 0; i < n; i++)
//    {
//        a += b * pow(-1, i);
//        add += 1.0 / a;
//        b += 2;
//    }
//    printf("%.3lf", add);
//    return 0;
//}


//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a = 0;
//    int sum = 0;
//    int add = 0;
//    for (int i = 1; i <= n; i++)
//    {
//            a += 1;
//            sum += a;
//            add += sum;
//    }
//    printf("%d", add);
//    return 0;
//}


//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int add = 0;
//    int a;
//    while (n != 0)
//    {
//        a = n % 10;
//        n /= 10;
//        add += a;
//    }
//    printf("%d", add);
//    return 0;
//}




//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int count = 0;
//    while (n != 1)
//    {
//        if (n % 2 == 0)
//        {
//            count++;
//            n /= 2;
//        }
//        else
//        {
//            count++;
//            n = n * 3 + 1;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}



//int main()
//{
//    int count = 0;
//    int i;
//    for (i = 9; i <= 2019; i++)
//    {
//        int k = i;
//        while (k != 0)
//        {
//            int a = k % 10;
//            if (a == 9)
//            {
//                count++;
//                break;
//            }
//            k /= 10;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}



//int main()
//{
//    int count = 0;
//    int n;
//    scanf("%d", &n);
//    double a, b, c;
//    double average;
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%lf %lf %lf", &a, &b, &c);
//        average = (a + b + c) / 3;
//        if (average < 60)
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}



//#include<math.h>
//int main()
//{
//    int m, n;
//    while (scanf("%d %d", &m, &n) != EOF)
//    {
//        int count = 0;
//        for (int i = m; i <= n; i++)
//        {
//            int add = 0;
//            int k = i;
//            while (k)
//            {
//                add += pow(k % 10,3);
//                k /= 10;
//            }
//            if (add == i)
//            {
//                printf("%d ", i);
//                count = 1;
//            }
//        }
//        if (!count)
//        {
//            printf("no");
//        }
//        printf("\n");
//    }
//    return 0;
//}



//int main()
//{
//    int i;
//    for (i = 10000; i <= 99999; i++)
//    {
//        int j = 10;
//        int add = 0;
//        int l[10] = { 0 };
//        int h = 0;
//        for ( h = 0;h < 4;h++)
//        {
//           int x = i % j;
//           int y = i / j;
//           l[h] = x * y;
//           j *= 10;
//        }
//        for (int v = 0; v < 4; v++)
//        {
//            add += l[v];
//        }
//        if (add == i)
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}



//int main()
//{
//    double a, b, c, d, e, f, g;
//    while (scanf("%lf %lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f, &g) != EOF)
//    {
//        double an[7];
//        an[0] = a; an[1] = b; an[2] = c; an[3] = d; an[4] = e; an[5] = f; an[6] = g;
//        double max = an[0];
//        double min = an[0];
//        double add = 0;
//        for (int i = 0; i < 7; i++)
//        {
//            if (max < an[i])
//            {
//                max = an[i];
//            }
//            if (min > an[i])
//            {
//                min = an[i];
//            }
//            add += an[i];
//        }
//        printf("%.2lf\n", (add - max - min) / 5);
//    }
//    return 0;
//}



//int main()
//{
//    int a;
//    scanf("%d", &a);
//    while (a)
//    {
//        int b = a % 10;
//        a /= 10;
//        printf("%d", b);
//    }
//
//    return 0;
//}



//void prin(int a)
//{
//    if (a > 5)
//    {
//        prin(a / 6);
//    }
//    printf("%d", a % 6);
//}
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    prin(a);
//    return 0;
//}



//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int add = 0;
//    int day = 1;
//    int count = 0;
//        while (count < a)
//        {
//            for (int i = 0; i < day&&count<a; i++)
//            {
//                add += day;
//                count++;
//            }
//            day++;
//        }
//    printf("%d", add);
//    return 0;
//}



//#include<math.h>
//int pn(int i)
//{
//    int count = 0;
//    int k = i;
//    while (k)
//    {
//        k /= 10;
//        count++;
//    }
//    int y = count;
//    int x = 1;
//    int num = 0;
//    for (int j = 0;y > x; j++)
//    {
//        int o = i / (int)pow(10, y - 1);
//        int q = i % (int)pow(10, x);
//        if (o != q)
//        {
//            num++;
//            break;
//        }
//        y--;
//        x++;
//    }
//    if (num)
//    {
//        return 0;
//    }
//    else
//    {
//        return 1;
//    }
//}
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//    {
//        int p = pn(i);
//        if (p)
//        {
//            printf("%d\n", i);
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int add(int a, int b)
//{
//    return a + b;
//}
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    printf("%d", add(a, b));
//}


//#include<stdio.h>
//int main()
//{
//    int x;
//    scanf("%d", &x);
//    printf("%d %d", x, 10 * x);
//    //printf("400.00");
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int a;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            for (int j = 0; j < a - 1; j++)
//            {
//                printf("* ");
//            }
//            printf("*");
//            printf("\n");
//        }
//    }
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int a;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 1; i <= a; i++)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            for (int j = i; j < a; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a;
//    while (scanf("%d", &a) != eof)
//    {
//        for (int i = 1; i <= a; i++)
//        {
//            for (int j = 0; j < a - i; j++)
//            {
//                printf("  ");
//            }
//            for (int j = 0; j < i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}




//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while(scanf("%d", &a)!=EOF)
//    {
//        for (int i = 1; i <= a; i++)
//        {
//            for (int j = 0; j < a - i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 0; j < i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//
//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 0; j < a - i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 1; i <= a; i++)
//        {
//            for (int j = i; j <= a; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 0; j < i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//        for (int i = 0; i <= a; i++)
//        {
//            printf("* ");
//        }
//        printf("\n");
//        for (int i = 0; i < a; i++)
//        {
//            printf(" ");
//            for (int j = 0; j < i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 0; j < a - i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            printf("* ");
//            for (int j = i; j < a; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//        printf("* \n");
//        for (int i = 0; i < a; i++)
//        {
//            printf("* ");
//            for (int j = 0; j <= i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 1; i < 2 * a + 1; i += 2)
//        {
//            for (int j = i; j < 2 * a + 1; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 0; j < i/2 + 1; j++)
//            {
//                printf("*");
//            }
//            printf("\n");
//        }
//        for (int i = 0; i <= a; i++)
//        {
//            printf("*");
//        }
//        printf("\n");
//        for (int i = 2; i < 2 * a + 2; i += 2)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = i / 2; j < a + 1; j++)
//            {
//                printf("*");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                printf(" ");
//            }
//                printf("*\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            for (int j = i + 1; j < a; j++)
//            {
//                printf(" ");
//            }
//            printf("*\n");
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            if (i == a - 1)
//            {
//                for (int j = 0; j < a; j++)
//                {
//                    printf("* ");
//                }
//                printf("\n");
//            }
//            else
//            {
//                for (int j = 0; j < i + 1; j++)
//                {
//                    if (j == 0 || j == i)
//                    {
//                        printf("* ");
//                    }
//                    else
//                    {
//                        printf("  ");
//                    }
//                }
//                printf("\n");
//            }
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    while (scanf("%d", &a) != EOF)
//    {
//        for (int i = 1; i <= a; i++)
//        {
//            for (int j = 1; j <= i; j++)
//            {
//                printf("%d ", j);
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//#include<stdio.h>
// 
//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//    int b = a * 3;
//    b--;
//    int k = b;
//    for (int i = 1; i <= a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            printf(" ");
//        }
//        --b;
//        for (int j = 1; j <= i; j++)
//        {
//            printf("*     ");
//        }
//        printf("\n");
//        for (int j = 0; j < b; j++)
//        {
//            printf(" ");
//        }
//        --b;
//        for (int j = 1; j <= i; j++)
//        {
//            printf("* *   ");
//        }
//        printf("\n");
//        for (int j = 0; j < b; j++)
//        {
//            printf(" ");
//        }
//        b--;
//        for (int j = 1; j <= i; j++)
//        {
//            printf("* * * ");
//        }
//        printf("\n");
//    }
//    for (int i = 1; i <= a; i++)
//    {
//        for (int j = 0; j < k; j++)
//        {
//            printf(" ");
//        }
//        printf("*\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    //找规律，n为8时，最少需要数组大小为arr[392][767]
//    char arr[800][800] = { 0 };
//    int n = 0;
//    scanf("%d", &n);
//    //找规律可以发现n与y（顶点在数组第一行的下标值）的关系
//    int y = 3 * pow(2, n - 1) - 1;
//    //初始化一个最小的三角形
//    arr[0][y] = '*';
//    arr[1][y - 1] = '*';
//    arr[1][y + 1] = '*';
//    arr[2][y - 2] = '*';
//    arr[2][y + 2] = '*';
//    arr[2][y] = '*';
//    //将现有的三角形复制到左下和右下
//    //n表示复制n-1次
//    for (int i = 1; i < n; i++)
//    {
//        int rang = (3 * pow(2, i - 1) - 1);
//        //被复制的范围是：横坐标为[0,rang]、纵坐标为[y-rang,y+rang]
//        //在外层循环中，x1代表当前遍历的行数，从0到rang（当前三角形的高度）遍历。 
//        // 在内层循环中，y1代表当前遍历的列数，从y-rang到y+rang（当前三角形所在列的范围）遍历。
//        // 然后，将当前位置上的元素（arr[x1][y1]）复制到左下方对应的位置（arr[x1 + rang + 1][y1 - rang - 1]）。
//        for (int x1 = 0; x1 <= rang; x1++)
//        {
//            for (int y1 = y - rang; y1 <= y + rang; y1++)
//            {
//                arr[x1 + rang + 1][y1 - rang - 1] = arr[x1][y1];
//            }
//        }
//        for (int x1 = 0; x1 <= rang; x1++)
//        {
//            for (int y1 = y - rang; y1 <= y + rang; y1++)
//            {
//                arr[x1 + rang + 1][y1 + rang + 1] = arr[x1][y1];
//            }
//        }
//    }
//    //打印树叶
//    for (int i = 0; i <= 3 * pow(2, n - 1) - 1; i++)
//    {
//        for (int j = 0; j <= 3 * pow(2, n) - 2; j++)
//        {
//            if (arr[i][j] == '*')
//                printf("%c", arr[i][j]);
//            else
//                printf(" ");
//        }
//        printf("\n");
//    }
//    //打印树干
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < y; j++)
//            printf(" ");
//        printf("*\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a[1000];
//    int n, x;
//    scanf("%d %d", &n, &x);
//    for (int i = 0; i <= n; i++)
//    {
//        a[i] = i;
//    }
//    int count = 0;
//    for (int i = 0; i <= n; i++)
//    {
//        while (a[i])
//        {
//            if (a[i] % 10 == x)
//            {
//                count++;
//            }
//            a[i] /= 10;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a[10];
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    for (int i = 9; i >= 0; i--)
//
//    {
//        printf("%d", a[i]);
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int n = 0; 
//    scanf("%d", &n);
//    int a[100];
//    int add = 0;
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//        add += a[i];
//    }
//    printf("%d", add);
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[1000];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int max = a[0];
//    int min = a[0];
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] > max)
//        {
//            max = a[i];
//        }
//        if (a[i] < min)
//        {
//            min = a[i];
//        }
//    }
//    printf("%d", max - min);
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = i; j < n; j++)
//        {
//            if (a[i] < a[j])
//            {
//                int t = a[i];
//                a[i] = a[j];
//                a[j] = t;
//            }
//        }
//    }
//    for (int i = 0; i < 5; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] == a[i + 1])
//        {
//            continue;
//        }
//        else
//        {
//            if (a[i] > a[i + 1])
//            {
//                for (int j = 0; j < n - 1; j++)
//                {
//                    if (a[j] < a[j + 1])
//                    {
//                        count++;
//                        break;
//                    }
//                }
//            }
//            else if (a[i] < a[i + 1])
//            {
//                for (int j = 0; j < n - 1; j++)
//                {
//                    if (a[j] > a[j + 1])
//                    {
//                        count++;
//                        break;
//                    }
//                }
//            }
//            break;
//        }
//    }
//    if (!count)
//    {
//        printf("sorted");
//    }
//    else
//    {
//        printf("unsorted");
//    }
//        return 0;
//}




//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int m;
//    scanf("%d", &m);
//    for (int i = 0; i < n; i++)
//    {
//        if ((m > a[i] && m < a[i + 1])|| (m >= a[n-1]&&i==n-1))
//        {
//            printf("%d %d ", a[i], m);
//        }
//        else if (m <= a[0]&&i==0)
//        {
//            printf("%d %d ", m, a[0]);
//        }
//        else
//        {
//            printf("%d ", a[i]);
//        }
//    }
//    return 0;
//}




//#include<stdio.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int m;
//    scanf("%d", &m);
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] != m)
//        {
//            printf("%d ", a[i]);
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int a[6000] = { 0 };
//    int b[3000] = { 0 };
//    int n;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &b[i]);
//    }
//    for (int i = 0; i < n; i++)
//    {
//        if (a[b[i]] == 0)
//        {
//            printf("%d ", b[i]);
//            a[b[i]]++;
//        }
//    }
//    return 0;
//}



//#include<stdio.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[200];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int m;
//    scanf("%d", &m);
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] == m)
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}


//
//#include<stdio.h>
//#include<math.h>
//
//int su(int i)
//{
//    int j;
//    for (j = 2; j <= sqrt(i); j++)
//    {
//        if (i % j == 0)
//        {
//            break;
//        }
//    }
//    if (j > sqrt(i))
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int count = 0;
//    for (int i = 2; i <= n; i++)
//    {
//        if (su(i))
//        {
//            printf("%d ", i);
//        }
//        else
//            count++;
//    }
//    printf("\n");
//    printf("%d", count);
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    double a[5][5];
//    for (int i = 0; i < 5; i++)
//    {
//        for (int j = 0; j < 5; j++)
//        {
//            scanf("%lf", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < 5; i++)
//    {
//        double add = 0;
//        for (int j = 0; j < 5; j++)
//        {
//            add += a[i][j];
//            printf("%.1lf ", a[i][j]);
//        }
//        printf("%.1lf\n", add);
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    int a[100][100];
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    int x, y;
//    scanf("%d %d", &x, &y);
//    printf("%d", a[x - 1][y - 1]);
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    int max = a[0][0];
//    int x = 0, y = 0;
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (max < a[i][j])
//            {
//                max = a[i][j];
//                x = i;
//                y = j;
//            }
//        }
//    }
//    printf("%d %d", x + 1, y + 1);
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    int b[100][100];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &b[i][j]);
//        }
//    }
//    int count = 0;
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (a[i][j] != b[i][j])
//            {
//                count++;
//            }
//        }
//    }
//    if (!count)
//    {
//        printf("Yes\n");
//    }
//    else
//    {
//        printf("No\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    int add = 0;
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//            if (a[i][j] > 0)
//            {
//                add += a[i][j];
//            }
//        }
//    }
//    printf("%d", add);
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[100][100];
//    int right = n - 1;
//    int left = 0;
//    int up = 0;
//    int down = n - 1;
//    int num = 1;
//    while (left <= right && up <= down)
//    {
//        for (int i = left; i <= right; i++)
//        {
//            a[up][i] = num;
//            num++;
//        }
//        up++;
//        for (int i = up; i <= down; i++)
//        {
//            a[i][right] = num;
//            num++;
//        }
//        right--;
//        for (int i = right; i >= left; i--)
//        {
//            a[down][i] = num;
//            num++;
//        }
//        down--;
//        for (int i = down; i >= up; i--)
//        {
//            a[i][left] = num;
//            num++;
//        }
//        left++;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}




//#include<stdio.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int i = 0, j = 0;
//    int a[100][100];
//    a[i][j] = 1;
//    int move = 1;
//    for(int num = 2; num <= n * n; num++)
//    {
//        if (i == 0 && move ==1 && j < n - 1)
//        {
//            j++;
//            a[i][j] = num;
//            move = -1;
//        }
//        else if (j == 0 && i < n - 1 && move == -1)
//        {
//            i++;
//            a[i][j] = num;
//            move = 1;
//        }
//        else if (j == n - 1 && move == 1)
//        {
//            i++;
//            a[i][j] = num;
//            move = -1;
//        }
//        else if (i == n - 1 && move == -1)
//        {
//            j++;
//            a[i][j] = num;
//            move = 1;
//        }
//        else if (move == 1)
//        {
//            i--;
//            j++;
//            a[i][j] = num;
//        }
//        else if (move == -1)
//        {
//            i++;
//            j--;
//            a[i][j] = num;
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    int b[100][100];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &b[i][j]);
//        }
//    }
//    double count = 0;
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (a[i][j] == b[i][j])
//            {
//                count++;
//            }
//        }
//    }
//    printf("%.2lf", (count * 100) / (double)(n * m));
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[100][100];
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    int num = 0;
//    for (int i = 0;i < n; i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            if (a[i][j] != 0)
//            {
//                num++;
//            }
//        }
//    }
//    if (num)
//    {
//        printf("NO");
//    }
//    else
//    {
//        printf("YES");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    int a[100][100];
//    for (int i = 0; i < n * m; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j=0; j < m; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            printf("%d ", a[j][i]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int a[100][100];
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    int k;
//    scanf("%d", &k);
//    char t;
//    int q, p;
//    for (int i = 0; i < k; i++)
//    {
//        getchar();
//        scanf("%c %d %d", &t, &q, &p);//q=1,p=2
//        if (t == 'r')
//        {
//            for (int x = 0; x < n; x++)
//            {
//                int z = a[q - 1][x];//z=a[1][0]
//                a[q - 1][x] = a[p - 1][x];//a[1][0]=a[2][0]
//                a[p - 1][x] = z;//a[2][0]=z
//            }
//        }
//        else if (t == 'c')
//        {
//            for (int x = 0; x < m; x++)
//            {
//                int z = a[x][q - 1];
//                a[x][q - 1] = a[x][p - 1];
//                a[x][p - 1] = z;
//            }
//        }
//        else if (t == 't')
//        {
//            continue;
//        }
//    }
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[500][500] = {0};
//    for (int k = 1; k <= n; k++)
//    {
//        for (int i = 0; i < k; i++)
//        {
//            if (i == 0)
//            {
//                a[k - 1][i] = 1;
//            }
//            else if (i == k - 1)
//            {
//                a[k - 1][i] = 1;
//            }
//            else
//            {
//                a[k - 1][i] = a[k - 2][i] + a[k - 2][i - 1];
//            }
//            printf("%5d", a[k - 1][i]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//#include <stdio.h>
//
//int main()
//{
//    char board[3][3];
//
//    for (int i = 0; i < 3; i++)
//    {
//        for (int j = 0; j < 3; j++)
//        {
//            scanf(" %c", &board[i][j]);
//        }
//    }
//
//    char ch = ' ';
//    int num = 0;
//
//    for (int i = 0; i < 3; i++)
//    {
//        for (int j = 0; j < 3; j++)
//        {
//            if (board[i][j] != 'O' && board[i][j] != ' ')
//            {
//                if ((board[i + 1][j] == board[i][j] && board[i + 2][j] == board[i][j]) ||
//                    (board[i][j] == board[i + 1][j + 1] && board[i][j] == board[i + 2][j + 2]) ||
//                    (board[i][j] == board[i][j + 1] && board[i][j] == board[i][j + 2]))
//                {
//                    ch = board[i][j];
//                    num = 1;
//                    break;
//                }
//            }
//        }
//
//        if (num == 1)
//        {
//            break;
//        }
//    }
//
//    if (ch == 'K')
//    {
//        printf("KiKi wins!");
//    }
//    else if (ch == 'B')
//    {
//        printf("BoBo wins!");
//    }
//    else if (ch == ' ')
//    {
//        printf("No winner!");
//    }
//
//    return 0;
//}




//#include<stdio.h>
//
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    char show[100][100] = { '.' };
//    for (int i = 1; i <= n; i++)
//    {
//        //scanf("\n");
//        //getchar();
//        for (int j = 1; j <= m; j++)
//        {
//            scanf("\n%c", &show[i][j]);
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (show[i][j] == '*')
//            {
//                continue;
//            }
//            else
//            {
//                char num = '0';
//                if (show[i + 1][j] == '*')
//                {
//                    num++;
//                }
//                if (show[i - 1][j] == '*')
//                {
//                    num++;
//                }
//                if (show[i][j + 1] == '*')
//                {
//                    num++;
//                }
//                if (show[i][j - 1] == '*')
//                {
//                    num++;
//                }
//                if (show[i - 1][j - 1] == '*')
//                {
//                    num++;
//                }
//                if (show[i - 1][j + 1] == '*')
//                {
//                    num++;
//                }
//                if (show[i + 1][j + 1] == '*')
//                {
//                    num++;
//                }
//                if (show[i + 1][j - 1] == '*')
//                {
//                    num++;
//                }
//                show[i][j] = num;
//            }
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            printf("%c", show[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    char a[100];
//    fgets(a, sizeof(a), stdin);
//    int sz = sizeof(a) - 1;
//    int num = 0;
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[i] >= '0' && a[i] <= '9')
//        {
//            num++;
//        }
//        if (a[i] >= 'a' && a[i] <= 'z')
//        {
//            num++;
//        }
//        if (a[i] >= 'A' && a[i] <= 'Z')
//        {
//            num++;
//        }
//    }
//    printf("%d", num);
//    return 0;
//}



//#include<stdio.h>
//#include<string.h>
//
//int main()
//{
//    char a[] = { "admin admin" };
//    char b[100];
//    fgets(b, sizeof(b), stdin);
//    if (b[strlen(b) - 1] == '\n') {
//        b[strlen(b) - 1] = '\0';
//    }
//    int c = strcmp(b, a);
//    
//    if (!c)
//    {
//        printf("Login Success!");
//    }
//    else
//    {
//        printf("Login Fail!");
//    }
//    return 0;
//}



//#include<stdio.h>
//#include<string.h>
//#include<stdlib.h>
//#include<math.h>
//
//int fn(int num)
//{
//    int i;
//    if (num > 1)
//    {
//        for (i = 2; i <= sqrt(num); i++)
//        {
//            if (num % i == 0)
//            {
//                break;
//            }
//        }
//        if (i > sqrt(num))
//        {
//            return 1;
//        }
//        else
//        {
//            return 0;
//        }
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//int main()
//{
//    char a[110];
//    int b[130];
//    for (int i = 0; i < 130; i++)
//    {
//        b[i] = 0;
//    }
//    fgets(a, sizeof(a), stdin);
//    if (a[strlen(a) - 1] == '\n')
//    {
//        a[strlen(a) - 1] = '\0';
//    }
//    int sz = sizeof(a) - 1;
//    for (int i = 0; i < sz; i++)
//    {
//        b[(int)a[i]]++;
//    }
//    int max, min;
//    max = b[0];
//    for (int i = 0; i < 130; i++)
//    {
//        if (b[i] > max)
//        {
//            max = b[i];
//        }
//    }
//    min = max;
//    for (int i = 0; i < 130; i++)
//    {
//        if (b[i] < min && b[i] > 0)
//        {
//            min = b[i];
//        }
//    }
//    int num = max - min;
//    if (fn(num))
//    {
//        printf("Lucky Word\n");
//        printf("%d", num);
//    }
//    else
//    {
//        printf("No Answer\n0");
//    }
//    return 0;
//}



//#include<stdio.h>
//#include<math.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int k = n;
//    int m = n;
//    int i = 0;
//    while (k/1000 != 0)
//    {
//        k /= 1000;
//        i++;
//    }
//    int a[4];
//    for (int j = 1; j <= i; j++)
//    {
//        a[j] = m % 1000;
//        m /= 1000;
//    }
//    printf("%d", n / (int)pow(1000, i));
//    for (int j = i; j > 0; j--)
//    {
//       /* if (j == 1)*/
//            printf(",%03d", a[j]);
//        /*else
//        {
//            printf("%,03d", a[j]);
//        }*/
//    }
//    return 0;
//}



//#include<stdio.h>
//#include<stdlib.h>
//#include<string.h>
//int main()
//{
//    int cap = 10;
//    char* num = (char*)malloc(cap * sizeof(char));
//    int size = 0;
//    int count = 0;
//    do
//    {
//        if (count)
//        {
//            size++;
//        }
//        scanf("%c", &num[size]);
//        count = 1;
//        if (size == cap)
//        {
//            cap *= 2;
//            num = (char*)realloc(num, cap * sizeof(char));
//        }
//
//    } while (num[size] != '\n');
//    if (num[strlen(num) - 1] == '\n')
//    {
//        num[strlen(num) - 1] = '\0';
//    }
//    int A = 0;
//    int B = 0;
//    int sz = (int)strlen(num);
//    for (int i = 0; i < sz; i++)
//    {
//        if (num[i] == 'A')
//        {
//            A++;
//        }
//        else if (num[i] == 'B')
//        {
//            B++;
//        }
//        else if (num[i] == 'O')
//        {
//            break;
//        }
//    }
//    if (A > B)
//    {
//        printf("A");
//    }
//    else if (B > A)
//    {
//        printf("B");
//    }
//    else
//        printf("E");
//    free(num);
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    getchar();
//    char a[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%c", &a[i]);
//    }
//    char b[2];
//    int c[2];
//    for (int l = 0; l < m; l++)
//    {
//        for (int i = 0; i < 2; i++)
//        {
//            scanf("%d", &c[i]);
//        }
//        for (int i = 0; i < 2; i++)
//        {
//            scanf(" %c", &b[i]);
//        }
//        for (int i = c[0]; i <= c[1]; i++)
//        {
//            if (a[i - 1] == b[0])
//            {
//                a[i - 1] = b[1];
//            }
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        printf("%c", a[i]);
//    }
//    return 0;
//}



//#include<stdio.h>
//
//int main()
//{
//    char a[100];
//    fgets(a, sizeof(a), stdin);
//    int sz = sizeof(a) - 1;
//    int b[100];
//    int j = 0;
//    int count = 0;
//    for (int i = 0; i < sz - 1; i++)
//    {
//        if (((a[i] >= 'A' && a[i] <= 'Z') || (a[i] >= 'a' && a[i] <= 'z')) && count == 0)
//        {
//            b[j] = a[i];
//            j++;
//            count = 1;
//        }
//        else if (a[i] == ' ')
//        {
//            count = 0;
//        }
//    }
//    for (int i = 0; i < j; i++)
//    {
//        if (b[i] >= 'a' && b[i] <= 'z')
//        {
//            b[i] -= 32;
//        }
//        printf("%c", b[i]);
//    }
//    return 0;
//}


//#include<stdio.h>
//
//int max(int a, int b, int c)
//{
//    if (a < b)
//    {
//        a = b;
//    }
//    if (a < c)
//    {
//        a = c;
//    }
//    return a;
//}
//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    int d = a + b;
//    int e = b + c;
//    double m;
//    m = (double)max(d, b, c) / (max(a, e, c) + max(a, b, e));
//    printf("%.2lf", m);
//    return 0;
//}


//#include<stdio.h>
//
//int fn(int i)
//{
//    int add = 0;
//    while (i)
//    {
//        add += i % 10;
//        i /= 10;
//    }
//    if (add % 5 == 0)
//    {
//        return 1;
//    }
//    else
//        return 0;
//}
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int count = 0;
//    for (int i = a; i <= b; i++)
//    {
//        if (fn(i))
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}


//#include<stdio.h>
//#include<math.h>
//
//long long int fn(long long int n)
//{
//    if (n < 9)
//    {
//        return n;
//    }
//    else
//    {
//        long long int total = 0;
//        while (n)
//        {
//            total += n % 10;
//            n /= 10;
//        }
//        return fn(total);
//    }
//}
//int main()
//{
//    long long int n = 0;
//    scanf("%lld", &n);
//    printf("%lld\n", fn(n));
//    return 0;
//}



//#include<stdio.h>
//
//int fn(int i)
//{
//    int num = 0;
//    while (i)
//    {
//        int a = i % 10;
//        if (a == 2)
//        {
//            num++;
//        }
//        i /= 10;
//    }
//    return num;
//}
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int add = 0;
//    for (int i = m; i <= n; i++)
//    {
//        add += fn(i);
//    }
//    printf("%d", add);
//    return 0;
//}


//#include<stdio.h>
//#include<stdlib.h>
//
//double fn(int nums[], int n)
//{
//    double add = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (nums[i] > 60)
//        {
//            add += 0.2;
//        }
//        else
//        {
//            add += 0.1;
//        }
//    }
//    return add;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int cap = 10;
//    int* nums = (int*)malloc(sizeof(int) * cap);
//    char ch;
//    int size = 0;
//    do
//    {
//        scanf("%d%c", &nums[size], &ch);
//        size++;
//        if (size == cap)
//        {
//            cap *= 2;
//            nums = (int*)realloc(nums, sizeof(int) * cap);
//        }
//    } while (ch != '\n');
//    double add = fn(nums, n);
//    printf("%.1lf", add);
//    return 0;
//}


//#include<stdio.h>
//#include<math.h>
//
//int fn(int i)
//{
//    int j = 0;
//    for (j = 2; j <= sqrt(i); j++)
//    {
//        if (i % j == 0)
//        {
//            break;
//        }
//    }
//    if (j > sqrt(i))
//    {
//        return i;
//    }
//    else
//    {
//        return 0;
//    }
//}
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int add = 0;
//    for (int i = m; i <= n; i++)
//    {
//        add += fn(i);
//    }
//    printf("%d", add);
//    return 0;
//}



//#include<stdio.h>
//#include<stdlib.h>
//
//int fn(int a, int b)
//{
//    if (a >= b)
//    {
//        return a - b;
//    }
//    else
//    {
//        return b - a;
//    }
//}
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int cap = 10;
//    int* num1 = (int*)malloc(sizeof(int) * cap);
//    int* num2 = (int*)malloc(sizeof(int) * cap);
//    char ch1, ch2;
//    int size1 = 0;
//    int size2 = 0;
//    int add1 = 0;
//    do
//    {
//        scanf("%d%c", &num1[size1], &ch1);
//        add1 += num1[size1];
//        size1++;
//        if (size1 == cap)
//        {
//            cap *= 2;
//            num1 = (int*)realloc(num1, sizeof(int) * cap);
//        }
//    } while (ch1 != '\n');
//    do
//    {
//        scanf("%d%c", &num2[size2], &ch2);
//        size2++;
//        if (size2 == cap)
//        {
//            cap *= 2;
//            num2 = (int*)realloc(num2, sizeof(int) * cap);
//        }
//    } while (ch2 != '\n');
//    int sum1;
//    int min = add1;
//    int l, k;
//    for (int i = 0; i < size2; i++)
//    {
//        sum1 = num2[i];
//        for (int j = i + 1; j <= size2; j++)
//        {
//            if (fn(add1, sum1) < min)
//            {
//                min = fn(add1, sum1);
//                l = i;
//                k = j;
//            }
//            sum1 += num2[j];
//        }
//    }
//    for (int i = l; i < k; i++)
//    {
//        printf("%d ", num2[i]);
//    }
//    free(num1);
//    free(num2);
//    return 0;
//}




//#include<stdio.h>
//#include<math.h>
//
//int fn(long long int n)
//{
//    int a = 0;
//    while (n)
//    {
//        n /= 10;
//        a++;
//    }
//    return a;
//}
//
//int en(long long int t)
//{
//    int i;
//    for (i = 2; i <= sqrt(t); i++)
//    {
//        if (t % i == 0)
//        {
//            break;
//        }
//    }
//    if (i > sqrt(t))
//    {
//        return 1;
//    }
//    else
//        return 0;
//}
//
//int main()
//{
//    long long int n;    
//    scanf("%lld", &n);
//    long long int k = n;
//    int a = fn(n);
//    int b[90];
//    for(int i=0;n != 0;i++)
//    {
//        b[i] = n % 10;
//        n /= 10;
//    }
//    long long int add = 0;
//    for (int i = 1; i < a; i++)
//    {
//        add = k * 10 + b[i];
//        k = add;
//    }
//    if (en(add))
//    {
//        printf("prime");
//    }
//    else
//    {
//        printf("noprime");
//    }
//    return 0;
//}


//#include<stdio.h>
//
//static int count;
//
//int bn(int n)
//{
//    int k = n;
//    int a[100];
//    int i = 0;
//    for (i = 0; k != 0; i++)
//    {
//        a[i] = k % 10;
//        k /= 10;
//    }
//    int add = 0;
//    int b = 0;
//    for (int j = 0; j < i; j++)
//    {
//        add = b * 10 + a[j];
//        b = add;
//    }
//    if (add == n)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//int an(int n)
//{
//    if (bn(n))
//    {
//        return count;
//    }
//    else
//    {
//        count++;
//        int k = n;
//        int a[100];
//        int i = 0;
//        for (i = 0; k != 0; i++)
//        {
//            a[i] = k % 10;
//            k /= 10;
//        }
//        int b = 0;
//        int add = 0;
//        for (int j = 0; j < i; j++)
//        {
//            add = b * 10 + a[j];
//            b = add;
//        }
//        n += add;
//        return an(n);
//    }
//    
//}
//
//int main()
//{
//    int m = 0;
//    scanf("%d", &m);
//    int n;
//    scanf("%d", &n);
//    int count = an(n);
//    if (count > 30)
//    {
//        printf("Impossible!");
//    }
//    else
//    printf("STEP=%d", count);
//    return 0;
//}



//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[100];
//    for(int i=0;i<n;i++)
//    scanf("%d", &a[i]);
//    int b[100];
//    int j = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] != pow((int)sqrt(a[i]), 2))
//        {
//            b[j] = a[i];
//            j++;
//        }
//    }
//    int max = b[0];
//    for (int i = 0; i < j; i++)
//    {
//        if (b[i] > max)
//        {
//            max = b[i];
//        }
//    }
//    printf("%d", max);
//    return 0;
//}


//#include<stdio.h>
//#include<stdlib.h>
//
//int a[10000];
//
//void an()
//{
//    a[0] = 0;
//    a[1] = 1;
//    for (int i = 2; i <= 10000; i++)
//    {
//        a[i] = a[i % 2] + a[i / 2];
//    }
//
//}
//
//void fn(int m)
//{
//    int min = m;
//    for (int i = 0; i <= m; i++)
//    {
//        if (a[i] == a[m])
//        {
//            min = i;
//        }
//    }
//    printf("%d %d\n", a[m], min);
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    an();
//    int m;
//    int b[100];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &b[i]);
//    }
//    int max = b[0];
//    for (int i = 0; i < n; i++)
//    {
//        if (b[i] > max)
//        {
//            max = b[i];
//        }
//    }
//    for (int i = 0 ; i < n; i++)
//    {
//        fn(b[i]);
//    }
//    return 0;
//}


//#include<stdio.h>
//
//int i = 0;
//int fn(int n, char a, char b, char c)
//{
//    if (n == 0)
//    {
//        return 1;
//    }
//    else
//    {
//        i++;
//    }
//    return i;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    char a = 'a', b = 'b', c = 'c';
//    int j = fn(n, a, b, c);
//    printf("%d", j);
//    return 0;
//}


//#include<stdio.h>
//
//int count = 0;
//int fn(int n)
//{
//    if (n == 0)
//    {
//        return count++;
//    }
//    else if (n > 0)
//    {
//        fn(n - 1);
//        fn(n - 2);
//    }
//    return count;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a = fn(n);
//    printf("%d", a);
//    return 0;
//}



//#include<stdio.h>
//
//long long int count = 1;
//long long int fn(int n)
//{
//    if (n == 1)
//    {
//        return count;
//    }
//    else
//    {
//        count *= n;
//        fn(n - 1);
//    }
//   
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    long long int a = fn(n);
//    printf("%lld", a);
//    return 0;
//}  


//void f(int N)
//{
//    int count = 0;
//    for (int i = 0; i < N; i++)
//    {
//        for (int j = 0; j < N; j++)
//        {
//            ++count;
//        }
//    }
//    for (int k = 0; k < 2 * N; k++)
//    {
//        count++;
//    }
//    int M = 10;
//    while (M--)
//    {
//        ++count;
//    }
//    printf("%d", count);
//}

//void f(int N)
//{
//    int count = 0;
//    for (int k = 0; k < 2 * N; ++k)
//    {
//        count++;
//    }
//    int M = 10;
//    while (M++)
//    {
//        ++count;
//    }
//    printf("%d", count);
//}
//void f(int N, int M)
//{
//    int count = 0;
//    for (int k = 0; k < N; k++)
//    {
//        ++count;
//    }
//    for (int k = 0; k < M; k++)
//    {
//        ++count;
//    }
//}
//const char* s(const char* str, char cha)
//{
//    while (*str != '\0')
//    {
//        if (*str == cha)
//        {
//            return str;
//        }
//        ++str;
//    }
//    return NULL;
//}
//void B(int* a, int n)
//{
//    assert(a);
//    for (size_t end = n; end > 0; --end)
//    {
//        int exchange = 0;
//        for (size_t i = 1; i < end; ++i)
//        {
//            if (a[i - 1] > a[i])
//            {
//                Swap(&a[i - 1], &a[i]);
//                exchange = 1;
//            }
//        }
//        if (!exchange)
//        {
//            break;
//        }
//    }
//}
//int B(int* a, int n, int x)
//{
//    assert(a);
//    int begin = 0;
//    int end = n;
//    while (begin < end)
//    {
//        int mid = begin + ((end - begin) >> 1);
//        if (a[mid] < x)
//        {
//            begin = mid + 1;
//        }
//        else if (a[mid] > x)
//        {
//            end = mid;
//        }
//        else
//        {
//            return mid;
//        }
//    }
//    return - 1;
//}
//long long f(size_t N)
//{
//    return N < 2 ? N : f(N - 1) * N;
//}

//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    char c[80];
//    gets(c);
//    char s;
//    scanf("%c", &s);
//    int i = 0;
//    for (i = 0; i <= strlen(c); i++)
//    {
//        if (c[i] >= '0' && c[i] <= '9')
//            c[i] = s;
//    }
//    for (i = 0; i <= strlen(c); i++)
//        printf("%c", c[i]);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    char ch[20];
//    scanf("%s", ch);
//    printf("%s", ch);
//    return 0;
//}

//#include<stdio.h>
//
//struct k {
//    int num;
//    char ch;
//    char c;
//    char m;
//    char p;
//   //char nm;
//}l;
//
//int main()
//{
//    int a = sizeof(l);
//    printf("%d", a);
//}

//#include<stdio.h>
//
//int main()
//{
//    int b;
//    char ch[10];
//    scanf("%d%s", &b, &ch);
//    printf("%d %s", b, ch);
//    return 0;
//}



//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    printf("[");
//    int i;
//    for (i = 1; i < pow(10, a) - 1; i++)
//    {
//        printf("%d,", i);
//    }
//    printf("%d]", i);
//    return 0;
//}

//#include<math.h>
//int a[100010];
//int* printNumbers(int n, int* returnSize) {
//    int k = pow(10, n);
//    int i;
//    for (i = 1; i < k; i++)
//        a[i - 1] = i;
//    *returnSize = --i;
//    return a;
//}

//#include<stdio.h>
//
//int fn(int a)
//{
//    if ((a % 4 == 0 && a % 100 != 0) || a % 400 == 0)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//int main()
//{
//    int year, mouth, day;
//    scanf("%d %d %d", &year, &mouth, &day);
//    int a[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    if (fn(year))
//    {
//        a[2] = 29;
//    }
//    int add = 0;
//    for (int i = 1; i < mouth; i++)
//    {
//        add += a[i];
//    }
//    add += day;
//    printf("%d", add);
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    char ch[] = "";
//    printf("%d", strlen(ch));
//    return 0;
//}


//#include<stdio.h>
//
//struct X { 
//    short s; 
//    int i;
//    //char c;
//}x;
//int main()
//{
//    printf("%d", sizeof(x));
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int b = a * a - a + 1;
//    for (int i = 0; i < a - 1; i++)
//    {
//        printf("%d+", b);
//        b += 2;
//    }
//    printf("%d", b);
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//    int start = 2;
//    int add = 0;
//    for (int i = 0; i < a; i++)
//    {
//        add += start;
//        start += 3;
//    }
//    printf("%d", add);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int b[2005];
//    double add = 0;
//    int count = 0;
//    int num = 0;
//    for (int i = 0; i < a; i++)
//    {
//        scanf("%d", &b[i]);
//    }
//    for (int i = 0; i < a; i++)
//    {
//        if (b[i] > 0)
//        {
//            count++;
//            add += b[i];
//        }
//        if (b[i] < 0)
//        {
//            num++;
//            //add += 1;
//        }
//    }
//    double aver = add / count;
//    if (count == 0)
//    {
//        aver = 0;
//    }
//    printf("%d %.1lf", num, aver);
//    return 0;
//}

//
//#include<stdio.h>
//
//int fn(int a[])
//{
//    int min = a[0];
//    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
//    {
//        if (min > a[i])
//        {
//            min = a[i];
//        }
//    }
//    return min;
//} 

//#include<stdio.h>
//
//int main()
//{
//    int kong = 0;
//    int zong = 20;
//    printf("%d", zong + zong / 2);
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    char ch[20];
//    for (int i = 0; i < 20; i++)
//    {
//        ch[i] = ' ';
//    }
//    int n = 7;
//    ch[n] = '*';
//    int right = n;
//    int left = n;
//    while(left>0)
//    {
//     
//        //printf("\n");
//        ch[right] = '*';
//        ch[left] = '*';
//        right++;
//        left--;
//        for (int i = 0; i < sizeof(ch) / sizeof(ch[0]); i++)
//        {
//            printf("%c", ch[i]);
//        }
//        printf("\n");
//    }
//    right--;
//    left++;
//    while (left != right)
//    {
//        ch[right] = ' ';
//        ch[left] = ' ';
//        left++;
//        right--;
//        for (int i = 0; i < sizeof(ch) / sizeof(ch[0]); i++)
//        {
//            printf("%c", ch[i]);
//        }
//        printf("\n");
//
//    }
//    return 0;
//}
//
//#include<stdio.h>
//#include<math.h>
//int mn(int n)
//{
//    int count = 0;
//    while (n)
//    {
//        count++;
//        n /= 10;
//    }
//    return count;
//}
//
//int ret(int n)
//{
//    int k = mn(n);
//    int l = n;
//    int add = 0;
//    for (int i = k; i > 0; i--)
//    {
//        add += (int)pow(n % 10, k);
//        n /= 10;
//    }
//    if (add == l)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//int main()
//{
//    //int n = 100000;
//    //scanf("%d", &n);
//    int num;
//    for (int i = 0; i <= 100000; i++)
//    {
//        num = ret(i);
//        if (num)
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}
//

//#include<stdio.h>
//
//int fn(int i,int a)
//{
//    int add = 0;
//    for (int j = 0; j <= i; j++)
//    {
//        add += a;
//        a *= 10;
//    }
//    return add;
//}
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int num = 0;
//    for (int i = 0; i < 5; i++)
//    {
//        int y = fn(i, a);
//        num += y;
//    }
//    printf("%d", num);
//    return 0;
//}

//#include<stdio.h>
////非递归
//int main()
//{
//    int a[100];
//    a[0] = 1;
//    a[1] = 1;
//    int b = 0;
//    scanf("%d", &b);
//    for (int i = 2; i < b; i++)
//    {
//        a[i] = a[i - 1] + a[i - 2];
//    }
//    printf("%d", a[b - 1]);
//    return 0;
//}
//
//
////递归
//
////int fn(int a)
////{
////    if (a == 1|| a == 2)
////    {
////        return 1;
////    }
////    else
////    {
////        return fn(a - 1) + fn(a - 2);
////    }
////}
////
////int main()
////{
////    int a;
////    scanf("%d", &a);
////    int k  = fn(a);
////    printf("%d", k);
////    return 0;
////}


#include<stdio.h>

//int fn(int a, int b)
//{
//    if (b == 0)
//    {
//        return 1;
//    }
//    else
//    return a * fn(a, b - 1);
//}
//
//int main()
//{
//    int a,b;
//    scanf("%d %d", &a, &b);
//    int c = fn(a, b);
//    printf("%d", c);
//    return 0;
//}


//int fn(int a)
//{
//    if (!a)
//    {
//        return 0;
//    }
//    else
//    return a % 10 + fn(a / 10);
//}
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int k = fn(a);
//    printf("%d", k);
//    return 0;
//}

//递归：
//int fn(int n)
//{
//    if (n == 1)
//    {
//        return 1;
//    }
//    else
//    return n * fn(n - 1);
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int k = fn(n);
//    printf("%d", k);
//    return 0;
//}

////非递归：
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int add = 1;
//    while (n)
//    {
//        add *= n;
//        n -= 1;
//    }
//    printf("%d", add);
//    return 0;
//}

//void fn(int a)
//{
//    if (!a)
//    {
//        ;
//    }
//    else
//    {
//        printf("%d ", a % 10);
//        fn(a / 10);
//    }
//}
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    fn(a);
//    return 0;
//}

//#include<stdio.h>
//
//int NumberOf1(int n) {
//    int count = 0;
//    while (n)
//    {
//        n = n & (n - 1);
//        count++;
//    }
//    return count;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int k = NumberOf1(n);
//    printf("%d", k);
//    return 0;
//}

//#include<stdio.h>

//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int l = m ^ n;
//    int count = 0;
//    while (l)
//    {
//        l = l & (l - 1);
//        count++;
//    }
//    printf("%d", count);
//    return 0;
//}

//int main()
//{
//    int a = 1;
//    int b = 2;
//    a = a ^ b;
//    b = a ^ b;
//    a = a ^ b;
//    printf("%d %d", a, b);
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int  i = 1;
//    switch (i)
//    {
//    case 1:
//        printf("1 ");
//    case 2:
//        printf("2 ");
//    }
//    return 0;
//}


//#include <stdio.h>
//int i;
//int main()
//{
//    i--;
//    if (i > sizeof(i))
//    {
//        printf(">\n");
//    }
//    else
//    {
//        printf("<\n");
//    }
//    return 0;
//}


//#include <stdio.h>
//
//int findSingleNumber(int arr[], int n) {
//    int result = 0;
//
//    for (int i = 0; i < n; i++) {
//        result ^= arr[i]; 
//    }
//
//    return result;
//}
//
//int main() {
//    int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4 };
//    int n = sizeof(arr) / sizeof(arr[0]);
//
//    int singleNumber = findSingleNumber(arr, n);
//    printf("只出现一次的数字是：%d\n", singleNumber);
//
//    return 0;
//}


//#include <stdio.h>
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    char b[sizeof(a) * 8 + 1];
//    char c[(sizeof(a) * 8 / 2) + 1];
//    char e[(sizeof(a) * 8 / 2) + 1];
//    int d = sizeof(a) * 8 - 1;
//    int m = 0;
//    int n = 0;
//    for (int i = d; i >= 0; i--)
//    {
//        b[d - i] = ((a >> i) & 1) + '0';
//    }
//    b[sizeof(a) * 8] = '\0';  
//    for (int i = 0; i < sizeof(a) * 8; i++)
//    {
//        if (i % 2 == 0)
//        {
//            c[m++] = b[i];
//        }
//        else
//        {
//            e[n++] = b[i];
//        }
//    }
//    c[m] = '\0';  
//    e[n] = '\0';  
//    printf("%s\n", c);
//    printf("%s\n", e);
//    return 0;
//}
// 
//#include <stdio.h>
//int i;
//int main()
//{
//    i--;
//    //i = -1
//    //10000000000000000000000000000001  原码
//    //11111111111111111111111111111110  反码
//    //11111111111111111111111111111111  补码    
//    /*if (i > sizeof(i))
//    {
//        printf(">\n");
//    }
//    else
//    {
//        printf("<\n");
//    }*/
//    printf("%ud", i);
//    return 0;
//}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 /**
  * Note: The returned array must be malloced, assume caller calls free().
  */
//int* findErrorNums(int* nums, int numsSize, int* returnSize)
//{
//    int* array1, * array2, i;
//    array1 = (int*)calloc(numsSize, sizeof(int));
//    array2 = (int*)malloc(sizeof(int) * 2);
//    for (i = 0; i < numsSize; i++)
//    {
//        array1[nums[i] - 1] += 1;
//    }
//    for (int j = 0; j < i; j++)
//    {
//        if (array1[j] == 2)
//            array2[0] = j + 1;
//        else if (array1[j] == 0)
//            array2[1] = j + 1;
//    }
//    *returnSize = 2;
//    return array2;
//
//
//}
//

//#include<assert.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    assert(n > 3);
//
//    return 0;
//}

#include<stdio.h>
//
//void a(int arr[10])
//{
//    arr[2] = 2;
//}
//
//int main()
//{
//    int arr[10] = { 0 };
//    a(arr);
//    printf("%d", arr[2]);
//    return 0;
//}

//#include<string.h>
//
//void a(char str[10000], int sz)
//{
//    //printf("\0");
//
//    for (int i = sz - 1; i >= 0; i--)
//    {
//        printf("%c", str[i]);
//    }
//    //printf("\0");
//}
//  
//int main()
//{
//    char str[10000];
//    fgets(str, sizeof(str), stdin);
//    int sz = (int)strlen(str);
//    if (str[sz - 1] == '\n')
//        str[sz - 1] = '\0';
//    a(str, sz - 1);
//    return 0;
//}

//#include<stdio.h>

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    char a[5] = "ABCD";
//    char b[5];
//    char c[5];
//    while (n > 4)
//    {
//        n -= 4;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        b[i] = a[i];
//    }
//    for (int i = 0; i < 4 - n; i++)
//    {
//        c[i] = a[n + i];
//    }
//    int j = 0;
//    for (int i = 4 - n; i < 4; i++)
//    {
//        c[i] = b[j];
//        j++;
//    }
//    c[4] = '\0';
//    printf("%s", c);
//    return 0;
//}

//int Strlen(char a[])
//{
//    int count = 0;
//    int i = 0;
//    while (a[i] != '\n')
//    {
//        count++;
//        i++;
//    }
//    return count;
//}
//
//int main()
//{
//    char a[10];
//    fgets(a, sizeof(a), stdin);
//    int b = Strlen(a);
//    printf("%d", b);
//    return 0;
//}

//#include<stdlib.h>
//#include<string.h>
//int main()
//{
//    int cap = 10;
//    int size = 0;
//    int* a = (int*)malloc(sizeof(int) * cap);
//    char ch;
//    do {
//        scanf("%d%c", &a[size], &ch);
//        size++;
//        while (size == cap)
//        {
//            cap *= 2;
//            a = (int*)realloc(a, sizeof(int) * cap);
//        }
//    } while (ch!='\n');
//    /*for (int i = 0; i < 3; i++)
//    {
//        printf("%d ", a[i]);
//    }*/
//    /*int sz = sizeof(a) / sizeof(a[0]);
//    printf("%d", sz);*/
//    int j[20];
//    int o[20];
//    int m = 0;
//    int n = 0;
//    for (int i = 0; i < size; i++)
//    {
//        if (i % 2 == 0)
//        {
//            o[n] = a[i];
//            n++;
//        }
//        else
//        {
//            j[m] = a[i];
//            m++;
//        }
//    }
//    printf("奇数位：");
//    for (int i = 0; i < m; i++)
//    {
//        printf("%d ", j[i]);
//    }
//    printf("\n");
//    printf("偶数位：");
//    for (int i = 0; i < n; i++)
//    {
//        printf("%d ", o[i]);
//    }
//    printf("\n");
//    return 0;
//}


//#include<stdio.h>
//#include<string.h>
//void Print(int* arr, int sz)
//{
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", *arr);
//        arr++;
//    }
//}
//
//int main()
//{
//    int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    Print(arr, sz);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int arr[] = { 2,1,3,6,4,5,9,8,7,6 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    for (int i = 0; i < sz-1; i++)
//    {
//        for (int j = 0; j < sz - 1 - i; j++)
//        {
//            if (arr[j] < arr[j + 1])
//            {
//                int t = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = t;
//            }
//        }
//    }
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    char str1[] = "hello bit.";
//    char str2[] = "hello bit.";
//    char* str3 = "hello bit.";
//    char* str4 = "hello bit.";
//    if (str1 == str2)
//        printf("str1 and str2 are same\n");
//    else
//        printf("str1 and str2 are not same\n");
//
//    if (str3 == str4)
//        printf("str3 and str4 are same\n");
//    else
//        printf("str3 and str4 are not same\n");
//
//    return 0;
//}

//#include<stdio.h>
//
//int b(char a1[], char a2[], int sz1, int sz2, char a3[])
//{
//    int count = 0;
//    if (sz1 != sz2)
//    {
//        return 0;
//    }
//    else
//    {
//        for (int i = 0; i < sz1; i++)
//        {
//            for (int j = 0; j < sz2; j++)
//            {
//                if (a1[i] == a2[j] && a3[j] == '0')
//                {
//                    a3[j] = '1';
//                    count++;
//                    break;
//                }
//            }
//        }
//        if (count == sz1 - 1)
//        {
//            return 1;
//        }
//        else
//        {
//            return 0;
//        }
//    }
//}
//
//int main()
//{
//    char a1[] = "ABCD";
//    char a2[] = "ACBD";
//    char a3[] = "0000";
//    int sz1 = sizeof(a1) / sizeof(a1[0]);
//    int sz2 = sizeof(a2) / sizeof(a2[0]);
//    int k = b(a1, a2, sz1, sz2, a3);
//    printf("%d", k);
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    int a[4][4];
//    int left = 0;
//    int up = 0;
//    int right = 3;
//    int down = 3;
//    int k = 1;
//    while (right > left && up < down)
//    {
//        for (int i = left; i <= right; i++)
//        {
//            a[up][i] = k;
//            k++;
//        }
//        up++;
//        for (int i = up; i <= down; i++)
//        {
//            a[i][right] = k;
//            k++;
//        }
//        right--;
//        for (int i = right; i >= left; i--)
//        {
//            a[down][i] = k;
//            k++;
//        }
//        down--;
//        for (int i = down; i >= up; i--)
//        {
//            a[i][left] = k;
//            k++;
//        }
//        left++;
//    }
//    for (int i = 0; i < 4; i++)
//    {
//        for (int j = 0; j < 4; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    int n = 0;
//    scanf("%d", &n);
//    for(int )
//    return 0;
//}

//#include <stdio.h>
//
//int search(int* matrix, int rows, int cols, int target) {
//    if (matrix == NULL || rows <= 0 || cols <= 0) {
//        return 0;
//    }
//    int row = 0;
//    int col = cols - 1;
//    while (row < rows && col >= 0) {
//        int value = matrix[row * cols + col];
//        if (value == target) {
//            return 1;
//        }
//        else if (value > target) {
//            col--;
//        }
//        else {
//            row++;
//        }
//    }
//    return 0;
//}
//
//int main() {
//    int matrix[4][4] = {
//        { 1, 2, 8, 9 },
//        { 2, 4, 9, 12 },
//        { 4, 7, 10, 13 },
//        { 6, 8, 11, 15 }
//    };
//    int rows = 4;
//    int cols = 4;
//    int target = 7;
//    int found = search((int*)matrix, rows, cols, target);
//    if (found) {
//        printf("Found\n");
//    }
//    else {
//        printf("Not found\n");
//    }
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int n = 1;
//    int a[5][5];
//    int i = 0;
//    for (int n = 1; n < 5; n++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (j == n - 1 || j == 0)
//            {
//                a[n][j] = 1;
//            }
//            else
//            {
//                a[n][j] = a[n - 1][j - 1] + a[n - 1][j];
//            }
//        }
//    }
//    for (int i = 0; i < 5; i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    char a;
//    char b[5] = "ABCD";
//    for (int i = 0; i < 5; i++)
//    {
//        a = b[i];
//        int count = 0;
//        int num = 0;
//        if (a != 'A')
//        {
//            count++;
//        }
//        else
//            num++;
//        if (a == 'C')
//        {
//            count++;
//        }
//        else
//            num++;
//
//        if (a == 'D')
//        {
//            count++;
//        }
//        else
//            num++;
//
//        if (a != 'D')
//        {
//            count++;
//        }
//        else 
//            num++;
//
//        if (count == 3 && num == 1)
//        {
//            a = b[i];
//            break;
//        }
//    }
//    printf("%c", a);
//    return 0;
//}

//#include<stdio.h>
//
//void menu()
//{
//    printf("*************************\n");
//    printf("*****1.add   2.sub ******\n");
//    printf("*****3.mul   4.div ******\n");
//    printf("*****0.exit        ******\n");
//}
//
//int add(int x, int y)
//{
//    return x + y;
//}
//
//int sub(int x, int y)
//{
//    return x - y;
//}
//
//int mul(int x, int y)
//{
//    return x * y;
//}
//
//int div(int x, int y)
//{
//    return x / y;
//}
//
//int main()
//{
//    menu();
//    int k;
//    int x, y;
//    do {
//        scanf("%d", &k);
//        int (*pfarr[5])(int x, int y) = {0, add, sub, mul, div};
//        if (k > 0 && k < 5)
//        {
//            scanf("%d %d", &x, &y);
//            int z = (*pfarr[k])(x, y);
//            printf("%d\n", z);
//        }
//        else if (k == 0)
//        {
//            printf("退出程序\n");
//        }
//        else
//        {
//            printf("输入错误，重新输入：>");
//        }
//    } while (k);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int a[10] = { 0 };
//    int b[] = { 1,2,3,4,5,1,2,3,4,6 };
//    int sz = sizeof(b) / sizeof(b[0]);
//    for (int i = 0; i < sz; i++)
//    {
//        a[b[i]]++;
//    }
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[b[i]] == 1)
//        {
//            printf("%d ", b[i]);
//        }
//    }
//    return 0;
//}

//#include <stdio.h>
//
//int fn(int a, int b);
//int ln(int u);
//int main()
//{
//    int a, b;
//    while (scanf("%d %d", &a, &b) != EOF)
//    {
//        int k = fn(a, b);
//        printf("%d\n", k);
//    }
//    return 0;
//}
//
//int fn(int a, int b)
//{
//    int l[14] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//    if (ln(a))
//        l[2] = 29;
//    int y = l[b];
//    return y;
//}
//
//int ln(int u)
//{
//    if ((u % 4 == 0 && u % 100 != 0) || u % 400 == 0)
//    {
//        return 1;
//    }
//    else
//        return 0;
//}

//#include<stdio.h>
//#include<string.h>
//
//int fn(int sz)
//{
//    if (sz < 8)
//        return 0;
//    else
//        return 1;
//}
//
//int en(char a[], int sz)
//{
//    char m;
//    if (a[0] >= '0' && a[0] <= '9')
//    {
//        return 0;
//    }
//    else
//    {
//        int b = 0;
//        int c = 0;
//        int d = 0;
//        int e = 0;
//        for (int i = 0; i < sz; i++)
//        {
//            if (a[i] >= 'a' && a[i] <= 'z')
//            {
//                b++;
//            }
//            else if (a[i] >= 'A' && a[i] <= 'Z')
//            {
//                c++;
//            }
//            else if (a[i] >= '0' && a[i] <= '9')
//            {
//                d++;
//            }
//            else
//            {
//
//                e++;
//            }
//            if (e)
//            {
//                m = a[i];
//                break;
//            }
//        }
//        //printf("%c\n", m);
//        printf("%d\n", e);
//        if ((b && c) || (b && d) || (c && d) && (e == 0))
//        {
//            return 1;
//        }
//        else
//        {
//            return 0;
//        }
//    }
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    char a[105];
//    for (int i = 0; i < n; i++)
//    {
//        fgets(a, sizeof(a), stdin);
//        int sz = (int)strlen(a) - 1;
//        int b = fn(sz);
//        int c = en(a, sz);
//        if (b && c)
//        {
//            printf("YES\n");
//        }
//        else
//        {
//            printf("NO\n");
//        }
//    }
//    return 0;
//} 


//#include<stdio.h>
//#include<stdlib.h>
////int main()
////{
////    int a;
////    a = printf("123");
////    printf("\n%d", a);
////    return 0;
////}
//
//int main()
//{
//    int cap = 10;
//    int size = 0;
//    char ch;
//    int* a = (int*)malloc(sizeof(int) * cap);
//    do {
//        scanf("%d%c", &a[size], &ch);
//        size++;
//        if (size == cap)
//        {
//            cap *= 2;
//            a = (int*)realloc(a, sizeof(int) * cap);
//        }
//    } while (ch != '\n');
//    int k = 0;
//    scanf("%d", &k);
//    int count = 0;
//    for (int i = 0; i < size; i++)
//    {
//        if (a[i] == k)
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    free(a);
//    return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
////int GetNumberOfK(int* data, int dataLen, int k)
////{
////    int count = 0;
////    for (int i = 0; i < dataLen; i++)
////    {
////        if (data[i] == k)
////        {
////            count++;
////        }
////    }
////    return count;
////}
//
//int convertInteger(int A, int B)
//{
//    int i = 0;
//    i = A ^ B;
//    long long int count = 0;
//    int y = 0;
//    while (i && y < 32)
//    {
//        if ((i & 1) == 1)
//        {
//            count++;
//        }
//        i = (i >> 1);
//        y++;
//    }
//    return count;
//}

//#include<stdio.h>

//int dominantIndex(int* nums, int numsSize) 
//{
//    int count = 0;
//    int max = nums[0];
//    int num;
//    for (int i = 1; i < numsSize; i++)
//    {
//        if (max < nums[i])
//        {
//            max = nums[i];
//            num = i;
//        }
//    }
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (i == num)
//        {
//            continue;
//        }
//        if (max < 2 * nums[i])
//        {
//            count = 1;
//            break;
//        }
//    }
//    if (count)
//    {
//        return -1;
//    }
//    else
//    {
//        return num;
//    }
//}
//#include<stdlib.h>
//int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
//{
//    int* p = (int*)malloc(sizeof(int) * 100);
//    int size = 0;
//    for (int i = 0; i < nums1Size; i++)
//    {
//        int count = 0;
//        for (int k = 0; k < i; k++)
//        {
//            if (nums1[i] == nums1[k])
//            {
//                count = 1;
//            }
//        }
//        if (count)
//        {
//            continue;
//        }
//        for (int j = 0; j < nums2Size; j++)
//        {
//            if (nums1[i] == nums2[j])
//            {
//                p[size] = nums1[i];
//                size++;
//                break;
//            }
//        }
//    }
//    *returnSize = size;
//    return p;
//}


//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    char a[1050];
//    fgets(a, sizeof(a), stdin);
//    int sz = (int)strlen(a) - 1;
//    for (int i = 0; i < sz; i++)
//    {
//        for (int j = 0; j < sz - i - 1; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                char t = a[j];
//                a[j] = a[j + 1];
//                a[j + 1] = t;
//            }
//        }
//    }
//    for(int i = 0;i<sz;i++)
//    printf("%c", a[i]);
//    return 0;
//}


//#include<stdio.h>
//
//int pivotIndex(int* nums, int numsSize)
//{
//    int add1 = 0;
//    int add2 = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        add2 += nums[i];
//    }
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (i == 0)
//        {
//            add1 = 0;
//        }
//        else
//        add1 += nums[i - 1];
//        add2 -= nums[i];
//        if (add1 == add2)
//        {
//            return i;
//        }
//    }
//    return -1;
//}   

//#include<stdio.h>
////#define size 10
////int main()
////{
////    char a['10'];
////    //int n = 3;
////    //char a[n][n + 2];
////    return 0;
////}
//#include<string.h>
//
//int main()
//{
//    char n[550];
//    fgets(n, sizeof(n), stdin);
//    int sz = (int)strlen(n) - 1;
//    int a[130] = { 0 };
//    int count = 1;
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[n[i]] == 0 && n[i] >= 0 && n[i] <= 127 && n[i] != 10)
//        {
//            count++;
//            a[n[i]] = 1;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}


//#include<stdio.h>
//
//int majorityElement(int* nums, int numsSize) 
//{
//    int a[50000] = { 0 };
//    for (int i = 0; i < numsSize; i++)
//    {
//        a[nums[i]]++;
//    }
//    int max = nums[0];
//    for (int i = 0; i < 50000; i++)
//    {
//        if (a[max] < a[i])
//        {
//            max = nums[i];
//        }
//    }
//    return max;
//}


//#include<stdio.h>
//
//int main()
//{
//    int a = 1;
//    int b;
//    printf("%d", b = a++);
//    return 0;
//}

//int* selfDividingNumbers(int left, int right, int* returnSize) 
//{
//    int size = 0;
//    int a[100000];
//    for (int i = left; i < right; i++)
//    {
//        int j = i;
//        int count = 1;
//        while (i)
//        {
//            if (i / (i % 10) != 0)
//            {
//                count = 0;
//            }
//            i /= 10;
//        }
//        if (count)
//        {
//            a[size] = j;
//            size++;
//        }
//    }
//    *returnSize = size;
//    return a;
//}

//int* productExceptSelf(int* nums, int numsSize, int* returnSize) 
//{
//    int a[numsSize];
//    int add = 1;
//    for (int j = 0; j < numsSize; j++)
//    {
//        add *= nums[j];
//    }
//    for (int i = 0; i < numsSize; i++)
//    {
//        a[i] = (add / nums[i]);
//    }
//    *returnSize = numsSize;
//    int* b = malloc(sizeof(int) * numsSize);
//    memcpy(b, a, sizeof(int) * numsSize);
//    return b;
//}  

#include<stdio.h>

//int main()
//{
//   /* int a = 1;
//    int b = 1;
//    a / b = 2;*/
//    return 0;
//}

//int Add(int num1, int num2) 
//{
//    //int count;
//    //int add = 0;
//    //while (num2)
//    //{
//    //    count = (num2 & 1);
//
//    //    num2 -= 1;
//
//    //}
//    //while (num1)
//    //{
//    //    count = (num1 & 1);
//    //    if (count)
//    //    {
//    //        add++;
//    //    }
//    //    num1 -= 1;
//
//    //}
//
//    return add;
//}
//
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int c = Add(a, b);
//    printf("%d", c);
//}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//    int a[numsSize];
//    int size = 0;
//    int count = 1;
//    for (int i = 0; i < numsSize; i++)
//    {
//        for (int j = 0; j < numsSize - i - 1; j++)
//        {
//            if (nums[j] < nums[j + 1])
//            {
//                nums[j] = nums[j] ^ nums[j + 1];
//                nums[j + 1] = nums[j] ^ nums[j + 1];
//                nums[j] = nums[j] ^ nums[j + 1];
//            }
//            if (nums[j] == nums[j + 1])
//            {
//                nums[j + 1] = 0;
//            }
//        }
//    }
//    int k = 0;
//    while (nums[k])
//    {
//        k++;
//    }
//    for (int l = k; l < numsSize; l++)
//    {
//        if (nums[l] != count)
//        {
//            a[size++] = count;
//        }
//        count++;
//    }
//    for (int i = 0; i < numsSize; i++)
//    {
//        /*int count = 0;
//        for (int j = 0; j < numsSize; j++)
//        {
//            if (nums[j] == i)
//            {
//                count = 1;
//                break;
//            }
//        }
//        if (count == 0)
//        {
//            a[size] = i;
//            size++;
//        }*/
//    }
//    *returnSize = size;
//    int* result = (int*)malloc(sizeof(int)*size);
//    memcpy(result, a, size * sizeof(int));
//    return result;
//}

//#include<stdio.h>
//
//int Add(int num1, int num2) {
//    while (num2 != 0) {
//        int sum = num1 ^ num2;
//        int carry = (num1 & num2) << 1;
//        num1 = sum;
//        num2 = carry;
//    }
//    return num1;
//}
//
//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int l = Add(a, b);
//    printf("%d", l);
//}

//#include<stdio.h>
//#include<stdlib.h>

//int findMaxConsecutiveOnes(int* nums, int numsSize) {
//    int a, b;
//    b = 0;
//    a = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        if(nums[i] == 1)
//        {
//            a++;
//        }
//        else
//        {
//            if (a > b)
//            {
//                b = a;
//                a = 0;
//            }
//            a = 0;
//        }
//    }
//    return a > b ? a : b;
//}
//
//int main()
//{
//    int cap = 10;
//    int size = 0;
//    char ch;
//    int* a = (int*)malloc(sizeof(int) * cap);
//    do {
//        scanf("%d%c", &a[size], &ch);
//        size++;
//        if (size == cap)
//        {
//            cap *= 2;
//            a = (int*)realloc(a, sizeof(int) * cap);
//        }
//    } while (ch != '\n');
//    int k = findMaxConsecutiveOnes(a, size);
//    printf("%d", k);
//    free(a);
//    return 0;
//}


//#include<stdio.h>
//#include<stdlib.h>
//
//int fn(int n)
//{
//    int add = 1;
//    for (int i = 2; i < n; i++)
//    {
//        if (n % i == 0)
//        {
//            add += i;
//        }
//    }
//    //if (add == n)
//    //{
//    //    return 1;
//    //}
//    //else
//    return add == n ? 1 : 0;
//}
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int count = 0;
//    for (int i = 2; i <= n; i++)
//    {
//        if (fn(i))
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n = 1001;
//    int ans = 0;
//    for (int i = 1; i <= n; ++i)
//    {
//        ans ^= i % 3;
//    }
//    printf("%d", ans);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    unsigned short x = 65530;
//    unsigned int y = x;
//    printf("%ud", y);
//}

//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    long long int n;
//    scanf("%lld", &n);
//    int a[100];
//    int k = 0;
//    if (n == 0)
//        a[0] = 0;
//    else
//    {
//        while (n)
//        {
//            a[k++] = n % 10;
//            n /= 10;
//        }
//    }
//    for (int i = 0; i < k; i++)
//    {
//        printf("%d", a[i]);
//    }
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//struct zimu {
//    char o[30];
//}x[10000];
//int main()
//{
//    char a[10009];
//    fgets(a, sizeof(a), stdin);
//    int sz = (int)strlen(a) - 1;
//    if (a[sz] == '\n')
//    {
//        a[sz] = '\0';
//    }
//    for (int i = 0; i < sz; i++)
//    {
//        if ((a[i] >= 'A' && a[i] <= 'Z') || (a[i] >= 'a' && a[i] <= 'z'))
//        {
//            ;
//        }
//        else
//            a[i] = ' ';
//    }
//    int size = 0;
//    int j = 0;
//    int b = 0;
//    for (int i = 0; i < sz; i++)
//    {
//        if (a[i] != ' ')
//        {
//            b = 0;
//            x[size].o[j++] = a[i];
//        }
//        else if (a[i] == ' ' && b == 0)
//        {
//            x[size].o[j] = '\0';
//            b = 1;
//            j = 0;
//            size++;
//        }
//    }
//    if (!b)
//    {
//        size++;
//    }
//    for (int i = size - 1; i > -1; i--)
//    {
//        int l = 0;
//        if (i)
//        {
//            while (x[i].o[l] != '\0')
//            {
//                printf("%c", x[i].o[l]);
//                l++;
//            }
//            printf(" ");
//        }
//        else
//            while (x[i].o[l] != '\0')
//            {
//                printf("%c", x[i].o[l]);
//                l++;
//            }
//    }
//    return 0;
//}

//#include<stdio.h>
//
////int main()
////{
////    int a[8];
////    &a[0]++;
////    return 0;
////}
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int a[40];
//    a[0] = 1;
//    a[1] = 1;
//    int i = 0;
//    for (i = 2; i < n; i++)
//    {
//        a[i] = a[i - 1] + a[i - 2];
//    }
//    int k = a[i - 1];
//    printf("%d", k);
//    return 0;
//}

//#include<stdio.h>
//#include<math.h>
//int main()
//{
//    int m;
//    double n;
//    while (scanf("%lf %d", &n, &m) == 2)
//    {
//        double add = 0;
//        for (int i = 0; i < m; i++)
//        {
//            add += n;
//            n = sqrt(n);
//        }
//        printf("%.2lf\n", add);
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }, * p = a + 5, * q = NULL;
//    *q = 0;
//    printf("%d %d\n", *p, *q);
//    return 0;
//}



/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//int* masterMind(char* solution, char* guess, int* returnSize) {
//    int* answer = (int*)calloc(2, sizeof(int));
//    int a[100] = { 0 };
//    for (int i = 0; i < 4; i++)
//    {
//        if (solution[i] == guess[i])
//        {
//            answer[0]++;
//            a[guess[i]]++;
//        }
//    }
//    for (int i = 0; i < 4; i++)
//    {
//        if (a[guess[i]]);
//        else
//        {
//            for (int j = 0; j < 4; j++)
//            {
//                if (guess[i] == solution[j])
//                {
//                    answer[1]++;
//                    break;
//                }
//            }
//            a[guess[i]]++;
//        }
//    }
//    *returnSize = 2;
//    return answer;
//}

//int* twoSum(int* numbers, int numbersLen, int target, int* returnSize) {
//    int* a = (int*)calloc(2, sizeof(int));
//    int b = 0;
//    for (int i = 0; i < numbersLen; i++)
//    {
//        if (numbers[i] > target)
//        {
//            continue;
//        }
//        //int c = target - numbers[i];
//        //int right = numbersLen - i;
//        //int left = i;
//        //int mid = (right + left) / 2;
//        //while (right > left)
//        //{
//        //    if (c == mid)
//        //    {
//        //        if (i > mid)
//        //        {
//        //            a[0] = mid + 1;
//        //            a[1] = i + 1;
//        //        }
//        //        else
//        //        {
//        //            a[0] = i + 1;
//        //            a[1] = mid + 1;
//        //        }
//        //        break;
//        //    }
//        //    else
//        //    {
//        //        if (c > numbers[mid])
//        //        {
//
//        //        }
//        //    }
//        //}
//        for (int j = i + 1; j < numbersLen; j++)
//        {
//            if ((numbers[i] + numbers[j]) == target)
//            {
//                    a[0] = i + 1;
//                    a[1] = j + 1;
//                    b = 1;
//            }
//            break;
//        }
//        if (b)
//        {
//            break;
//        }
//    }
//    *returnSize = 2;
//    return a;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    int cap = 10;
//    int size = 0;
//    float* a = (float*)malloc(sizeof(float) * cap);
//    char ch = ' ';
//    do {
//        scanf("%f%c", &a[size], &ch);
//        size++;
//        if (size == cap)
//        {
//            cap *= 2;
//            a = (float*)realloc(a, sizeof(float) * cap);
//        }
//    } while (ch == ' ');
//    //for (int i = 0; i < size; i++)
//    //{
//    //    for (int j = 0; j < size - 1 - i; j++)
//    //    {
//    //        if (a[j] > a[j + 1])
//    //        {
//    //            int t = a[j];
//    //            a[j] = a[j + 1];
//    //            a[j + 1] = t;
//    //        }
//    //    }
//    //}
//    float c = 0;
//    int l = 0;
//    int b = 0;
//    for (int i = 0; i < size; i++)
//    {
//        b = 0;
//        if (a[i] == 0.5)
//            continue;
//        for (int j = i; j < size; j++)
//        {
//            if (a[j] != 0.5)
//            {
//                if (a[i] == a[j])
//                {
//                    b++;
//                    if (i != j)
//                        a[j] = 0.5;
//                }
//            }
//        }
//        if (b % 2 == 1)
//        {
//            c = a[i];
//            break;
//        }
//        a[i] = 0.5;
//    }
//    //for (int i = 0; i < size; i++)
//    //{
//    //    int b = 1;
//    //    if (i == size - 1)
//    //    {
//    //        c = a[i];
//    //        break;
//    //    }
//    //    for (int j = i + 1; j < size; j++)
//    //    {
//    //        if (a[i] == a[j])
//    //        {
//    //            b++;
//    //        }
//    //        else
//    //        {
//    //            if (b % 2 == 1)
//    //            {
//    //                c = a[i];
//    //                l = 1;
//    //            }
//    //            i = j - 1;
//    //            break;
//    //        }
//    //    }
//    //    if (l)
//    //    {
//    //        break;
//    //    }
//    //}
//    int k = (int)c;
//    printf("%d", k);
//    free(a);
//    return 0;
//}

//int findPeakElement(int* nums, int numsLen) {
//
//    for (int i = 0; i < numsLen; i++)
//    {
//        if (i == 0)
//        {
//            if (nums[0] > nums[1])
//            {
//                return 0;
//            }
//        }
//        else if (i == numsLen - 1)
//        {
//            if (nums[i] > nums[i - 1])
//            {
//                return (numsLen - 1);
//            }
//
//        }
//        else
//        {
//            if (nums[i] > nums[i + 1] && nums[i] > nums[i - 1])
//            {
//                return i;
//            }
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    unsigned char i = 7;
//    //0000 0111 原码
//    //1111 1000 反码
//    //1111 1001 补码
//    //算术提升
//    //0000 0000 0000 0000 0000 0000 1111 1001
//    //反码：0000 0000 0000 0000 0000 0000 1111 1000
//    //原码：1111 1111 1111 1111 1111 1111 0000 0111
//    int j = 0;
//    for (; i > 0; i -= 3)
//    {
//        ++j;
//    }
//    printf("%d\n", j);
//    return 0;
//}

//#define MAX 255
//int main()
//{
//    unsigned char A[MAX], i;
//    for (i = 0; i <= MAX; i++)
//        A[i] = i;
//    return 0;
////}
//
//#include <stdio.h>
//
//int main()
//{
//    long long int n, k;
//    scanf("%lld %lld", &n, &k);
//    long long int count = 0;
//    if (k == 0)
//    {
//        printf("%ld\n", n * n);
//    }
//    else
//    {
//        for (long j = k + 1; j <= n; j++)
//        {
//            long help = n % j < k ? 0 : (n % j) - k + 1;
//            count += (j - k) * (n / j) + help;
//        }
//        printf("%ld\n", count);
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    long n, k = 0;
//    long count = 0;
//    while (~scanf("%ld %ld", &n, &k))
//    {
//        if (k == 0)
//        {
//            printf("%ld\n", n * n);
//            continue;
//        }
//        for (long j = k + 1; j <= n; j++)
//        {
//            long help = n % j < k ? 0 : (n % j) - k + 1;
//            count += (j - k) * (n / j) + help;
//        }
//        printf("%ld\n", count);
//    }
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    char a[1009];
//    fgets(a, sizeof(a), stdin);
//    int n;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        printf("%c", a[i]);
//    }
//    return 0;
//} 


//int:
//#include<stdio.h>
//#include<stdlib.h>
// 
//int camp(const void* a1, const void* a2)
//{
//    return (*(int*)a1 - *(int*)a2);
//}
//
//
//int main()
//{
//    int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
//    size_t sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), camp);
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    printf("\n");
//    return 0;
//}
//
//
//
//结构体：
//#include<stdio.h>
//#include<stdlib.h>
//#include<string.h>
//
//struct fn {
//    char name[20];
//    int age;
//};
//
//int  cmp_name(const void* a1, const void* a2)
//{
//    return strcmp(((struct fn*)a1)->name , ((struct fn*)a2)->name);
//}
//
//int  cmp_age(const void* a1, const void* a2)
//{
//    return (((struct fn*)a1)->age - ((struct fn*)a2)->age);
//}
//
//void test1()
//{
//    struct fn a[] = {{"zhangsan", 18}, {"lisi", 35}};
//    qsort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]), cmp_age);
//}
//void test2()
//{
//    struct fn a[] = { {"zhangsan", 18}, {"lisi", 35} };
//    qsort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]), cmp_name);
//}
//
//int main()
//{
//    test1();
//    test2();
//    return 0;
//}
//
//
//
//char:
//#include<stdio.h>
//#include<stdlib.h>
// 
//int camp(const void* a1, const void* a2)
//{
//    return (*(char*)a2 - *(char*)a1);
//}
//
//
//int main()
//{
//    char arr[] = { '9', '8', '7', '6', '\0'};
//    size_t sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), camp);
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%c ", arr[i]);
//    }
//    printf("\n");
//    return 0;
//}

//#include<stdio.h>
//
//int cmp(const void* a1, const void* a2)
//{
//    return *(int*)a1 - *(int*)a2;
//}
//
//void  Swap(void* a1, void* a2, size_t wide)
//{
//    for (int i = 0; i < wide; i++)
//    {
//        char t = *((char*)a1 + i);
//        *((char*)a1 + i) = *((char*)a2 + i);
//        *((char*)a2 + i) = t;
//    }
//}
//
//void bubble_line(const void* arr, size_t sz, size_t wide, int (*cmp)(const void* a1, const void* a2))
//{
//    for (int i = 0; i < sz - 1; i++)
//    {
//        for (int j = 0; j < sz - 1 - i; j++)
//        {
//            if (cmp((char*)arr + j * wide, (char*)arr + (j + 1) * wide) > 0)
//            {
//                Swap((char*)arr + j * wide, (char*)arr + (j + 1) * wide, wide);
//            }
//        }
//    }
//}
//
//int main()
//{
//    int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    bubble_line(arr, sz, sizeof(arr[0]), cmp);
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    printf("\n");
//    return 0;
//}

//#include <stdio.h>
//#define N 2
//#define M N + 1
//#define NUM (M + 1) * M / 2
//int main()
//{
//    printf("%d\n", NUM);
//    return 0;
//}
//
////假设环境是x86环境，程序输出的结果是啥？ 
//#include <stdio.h>
//int main()
//{
//    int a[5][5];
//    int(*p)[4];
//    p = a;
//    printf("%p,%d\n", &p[4][2] - &a[4][2], &p[4][2] - &a[4][2]);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    char* a[] = { "work","at","alibaba" };
//    char** pa = a;
//    pa++;
//    printf("%s\n", *pa);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    char* c[] = { "ENTER","NEW","POINT","FIRST" };
//    char** cp[] = { c + 3,c + 2,c + 1,c };
//    char*** cpp = cp;
//    printf("%s\n", **++cpp);
//    printf("%s\n", *-- * ++cpp + 3);
//    printf("%s\n", *cpp[-2] + 3);
//    printf("%s\n", cpp[-1][-1] + 1);
//    return 0;
//}

//#include<stdio.h>
//
//int my_strlen1(char a[])
//{
//    int b = 0;
//    while (a[b] != '\0')
//    {
//        b++;
//    }
//    return b;
//}
//
//int my_strlen2(char *a)
//{
//    if (*a != '\0')
//    {
//        return 1 + my_strlen2(a + 1);
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//int my_strlen3(char* a)
//{
//    char* b = a;
//    while (*a)
//    {
//        a++;
//    }
//    return a - b;
//}
//
//int main()
//{
//    char a[] = "abc";
//    int i = my_strlen3(a);
//    printf("%d\n", i);
//    return 0;
//}
//
//#include<stdio.h>
//#include <assert.h>
//void my_strcpy(char* a1, char* a2)
//{
//    assert(a1 != NULL);
//    assert(a2 != NULL);
//    while (*a2++ = *a1++)
//    {
//        ;
//    }
//}
//
//int main()
//{
//    char a1[10] = "abc";
//    char a2[] = {0};
//    my_strcpy(a1, a2);
//    printf("%s", a2);
//    return 0;
//}
//#include<stdio.h>
//void my_strcat(char* a1, char* a2)
//{
//    while (*a1)
//    {
//        a1++;
//    }
//    while (*a1++ = *a2++)
//    {
//        ;
//    }
//}
//int main()
//{
//    char a1[] = "abc";
//    char a2[] = "ef";
//    my_strcat(a1, a2);
//    printf("%s", a1);
//    return 0;
//}
//#include<stdio.h>
//#include<string.h>
//#include<stdlib.h>
//#include<conio.h>
//#define HH printf("%-10s%-10s%-10s%-10s%-10s%-10s\n","学号","姓名","性别","年龄","电话","地址")
//int n = 0;
//typedef struct stu
//{
//	char name[10];//姓名 
//	long int num;//学号 
//	char sex[4];//性别
//	int age;//年龄
//	char phone[15];//电话号码
//	char address[10];//地址 
//}stu;
//stu s[400];
//
//void menu();
//void add();//添加同学的信息
//void showall();//显示全部同学的信息  
//void query();//按照姓名或者学号查找同学的信息 
//void dele();//按照姓名删除同学的信息
//void sort();//按照学号或者年龄排序
//void revise();//按照学号修改信息
//void quit();//退出主程序
//
//void menu()
//{
//	printf("--------学生信息管理系统--------\n");
//	printf("------1、添加信息：------\n");
//	printf("------2、显示全部信息：\n------");
//	printf("------3、查找信息：------\n");
//	printf("------4、删除信息：------\n");
//	printf("------5、信息排序：------\n");
//	printf("------6、修改信息：------\n");
//	printf("------0、退出主程序------\n");
//	printf("请选择你要选择的功能：0~6：");
//}
//
//void add()
//{
//	int N, a = 1;
//	system("cls");
//	printf("请输入要添加的个数N:");
//	scanf("%d", &N);
//	getchar();
//	while (N > 0)
//	{
//		printf("请按照一下顺序添加信息:\n");
//		printf("学号 姓名 性别(b/g) 年龄 电话 地址\n");
//		scanf("%d", &s[n].num);
//		getchar();
//		fgets(s[n].name, sizeof(s[n].name), stdin);
//		fgets(s[n].sex, sizeof(s[n].sex), stdin);
//		scanf("%d", &s[n].age);
//		getchar();
//		fgets(s[n].phone, sizeof(s[n].phone), stdin);
//		//scanf("%ld%s%s%d%s%s",&s[n].num,&s[n].name,&s[n].sex,&s[n].age,&s[n].phone,&s[n].address);
//		n++;
//
//		N--;
//	}
//
//	printf("数据已经输入完成!\n");
//
//}
//
//void showall()
//{
//	int i;
//	printf("%-10s%-10s%-10s%-10s%-10s%-10s\n", "学号", "姓名", "性别", "年龄", "电话", "地址");
//	for (i = 0; i < n; i++)
//	{
//		printf("%d  %s  %s  %d %s %s", s[i].num, s[i].name, s[i].sex, s[i].age, s[i].phone, s[i].address);
//		//printf("%s 姓名 性别(b/g) 年龄 电话 地址\n");
//	}
//}
//
//void query()
//{
//	int i, m, l, j, k;
//	char str[10];
//	system("cls");
//	printf("查找学生的信息。\n");
//	printf("------请输入查询的依据------");
//	printf("[1]学号\n");
//	printf("[2]姓名\n");
//	scanf("%d", &m);
//	getchar();
//	if (m == 1)
//	{
//		printf("请输入学生学号：");
//		scanf("%d", &l);
//		getchar();
//		for (i = 0; i < n; i++)
//			if (l == s[i].num)
//			{
//				k = 1; j = i;
//			}
//	}
//	else if (m == 2)
//	{
//		printf("请输入学生姓名：");
//		scanf("%s", &str);
//		getchar();
//		for (i = 0; i < n; i++)
//			if (!strcmp(s[i].name, str))
//			{
//				k = 1; j = i;
//			}
//	}
//	if (k == 1)
//	{
//		printf("查询结果如下：\n");
//		printf("学号 姓名 性别 年龄 电话 地址\n");
//		
//			printf("%d %s %s %d %s %s", s[j].num, s[j].name, s[j].sex, s[j].age, s[j].phone, s[j].address);
//		
//	}
//	else
//	{
//		printf("未查到该生信息！\n");
//	}
//}
//
//void dele()
//{
//	int k = 0, j, i;
//	char str[10];
//	system("cls");
//	printf("请输入要删除同学的姓名：\n");
//	fgets(str, sizeof(str), stdin);
//	for (i = 0; i < n; i++)
//	{
//		if (strcmp(s[i].name, str) == 0)
//		{
//			k = 1, j = i;
//		}
//	}
//	if (k == 1)
//	{
//		for (i = j; i < n - 1; i++)
//			s[i] = s[i + 1];
//		n--;
//		printf("删除成功!\n");
//	}
//	else
//	{
//		printf("未查到该生信息！\n");
//	}
//}
//
//void sort()
//{
//	int m, i, j;
//	struct stu temp;
//	next:
//	system("cls");
//	printf("------请选择排序的依据------\n");
//	printf("[1]学号\n");
//	printf("[2]年龄\n");
//	scanf("%d", &m);
//	getchar();
//	if (m == 1)
//	{
//		for (i = 0; i < n - 1; i++)
//		{
//			for (j = i + 1; j < n - 1 - j; j++)
//			{
//
//				if (s[j].num > s[j + 1].num)
//				{
//					temp = s[j + 1];
//					s[j + 1] = s[j];
//					s[j] = temp;
//				}
//			}
//		}
//	}
//	else if (m == 2)
//	{
//	     for (i = 0; i < n - 1; i++)
//					{
//						for (j = i + 1; j < n - 1 - j; j++)
//						{
//							if (s[j].age > s[j + 1].age)
//							{
//								temp = s[j + 1];
//								s[j + 1] = s[j];
//								s[j] = temp;
//							}
//							//else if (s[i].age == s[j].age)
//							//{
//							//	if (s[i].num > s[j].num)
//							//	{
//							//		temp = s[i];
//							//		s[i] = s[j];
//							//		s[j] = temp;
//							//	}
//							//}
//						}
//					}
//				
//	}
//    else
//    {
//			printf("指令错误！");
//			goto next;
//	}
//			
//		
//	
//}
//
//void revise()
//{
//	int i;
//	char name[8];
//	printf("修改学生的信息。\n");
//	printf("请输入要修改学生的姓名：\n");
//	fgets(name, sizeof(name), stdin);
//	for (i = 0; i < n; i++)
//	{
//		if (strcmp(name, s[i].name) == 0)
//		{
//			printf("成功找到！\n");
//			printf("学号 姓名 性别 年龄 电话 地址\n");
//			printf("%d %s %s %d %s %s", s[i].num, s[i].name, s[i].sex, s[i].age, s[i].phone, s[i].address);
//			printf("请分别进行修改：\n");
//			printf("学号 姓名 性别 年龄 电话 地址\n");
//			scanf("%d", &s[n].num);
//			getchar();
//			fgets(s[n].name, sizeof(s[n].name), stdin);
//			fgets(s[n].sex, sizeof(s[n].sex), stdin);
//			scanf("%d", &s[n].age);
//			getchar();
//			fgets(s[n].phone, sizeof(s[n].phone), stdin);
//		}
//	}
//}
//int main()
//{
//	int choice;
//	int count = 1;
//	while (1)
//	{
//		menu();
//		scanf("%d", &choice);
//		getchar();
//		switch (choice)
//		{
//		case 1:add(); break;
//		case 2:showall(); break;
//		case 3:query(); break;
//		case 4:dele(); break;
//		case 5:sort(); break;
//		case 6:revise(); break;
//		case 0:count = 0;
//		}
//		if (!count)
//		{
//			break;
//		}
//	}
//	printf("请按任意键继续......\n");
//	return 0;
//}


//#include<stdio.h>
//
//int main()
//{
//    double j = 1;
//    double add = 0;
//    for (int i = 1; i < 101; i++)
//    {
//        add = add + j / i;
//        j *= -1;
//    }
//    printf("%lf", add);
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//int my_strcmp(const char* arr1, const char* arr2, size_t sz)
//{
//    for (int i = 0; i <= sz; i++)
//    {
//        if (*arr1 - *arr2)
//        {
//            return *arr1 - *arr2;
//        }
//        arr1++;
//        arr2++;
//        //if (*arr1 == '\0')
//        //{
//        //    if (*arr2 == '\0')
//        //    {
//        //        return 0;
//        //    }
//        //    else
//        //    {
//        //        return -1;
//        //    }
//        //}
//    }
//    return 0;
//}
//
//int main()
//{
//    char arr1[] = "abcd";
//    char arr2[] = "abdd";
//    size_t sz = strlen(arr1);
//    int k = my_strcmp(arr1, arr2, sz);
//    if (!k)
//    {
//        printf("==");
//    }
//    else if(k < 0)
//    {
//        printf("<");
//    }
//    else
//    {
//        printf(">");
//    }
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//char* my_strstr(char* arr1, char* arr2, int sz1, int sz2)
//{
//    char* s1 = NULL;
//    char* s2 = NULL;
//    int i = 0;
//    for (i = 0; i <= sz1 - sz2; i++)
//    {
//        if (*arr1 == *arr2)
//        {
//            int k = 0;
//            s1 = arr1;
//            s2 = arr2;
//            while (*s1 == *s2)
//            {
//                s1++;
//                s2++;
//                k++;
//                if (k == sz2)
//                {
//                    return arr1;
//                }
//            }
//        }
//        arr1++;
//    }
//    return NULL;
//}
//
//int main()
//{
//    char arr1[] = { "abcdef" };
//    char arr2[] = { "cde" };
//    int sz1 = (int)strlen(arr1);
//    int sz2 = (int)strlen(arr2);
//    char* p = my_strstr(arr1, arr2, sz1, sz2);
//    printf("%s", p);
//    return 0;
//}

//#include<stdio.h>
//
//char* my_strncpy(char* arr2, const char* arr1, int n)
//{
//    char* s = arr2;
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        *arr2 = *arr1;
//        arr2++;
//        arr1++;
//    }
//    *arr2 = '\0';
//    return s;
//}
//int main()
//{
//    char arr1[] = "abcdef";
//    char arr2[10] = { 0 };
//    char* p = my_strncpy(arr2, arr1, 3);
//    printf("%s", p);
//    return 0;
//}

//#include<stdio.h>
//#include<assert.h>
//char* my_strcat(char* arr1, const char* arr2)
//{
//    char* s = arr1;
//    assert(s);
//    while (*arr1)
//    {
//        arr1++;
//    }
//    while ((*arr1++ = *arr2++))
//    {
//        ;
//    }
//    return s;
//}
//int main()
//{
//    char arr1[20] = "Hello ";
//    char arr2[] = "world";
//    char* p = my_strcat(arr1, arr2);
//    printf("%s", p);
//    return 0;
//}

//#include<stdio.h>
//#include<assert.h>
//void* my_memcpy(void* a2, const void* a1, size_t n)
//{
//    void* s = a2;
//    assert(s);
//    for (int i = 0; i < n; i++)
//    {
//        *((char*)a2) = *((char*)a1);
//        a2 = (char*)a2 + 1;
//        a1 = (char*)a1 + 1;
//    }
//    return s;
//}
//int main()
//{
//    int a1[] = { 1,2,3,4,5,6,7,8,9 };
//    int a2[10] = { 0 };
//    my_memcpy(a2, a1, sizeof(a1[0])*4);
//    int i = 0;
//    for (i = 0; i < 4; i++)
//    {
//        printf("%d ", a2[i]);
//    }
//
//    return 0;
//}

//#include<stdio.h>
//#include<assert.h>
//void* my_memmove(void* a1, const void* a2, int n)
//{
//    void* s = a1;
//    assert(s);
//    if (a1 < a2)
//    {
//        for (int i = 0; i < n; i++)
//        {
//            *((char*)a1) = *((char*)a2);
//            a1 = (char*)a1 + 1;
//            a2 = (char*)a2 + 1;
//        }
//    }
//    else if(a1 == a2)
//    {
//        return s;
//    }
//    else
//    {
//        for (int i = 0; i < n; i++)
//        {
//            *((char*)a1 + n - i - 1) = *((char*)a2 + n - i - 1);
//        }
//    }
//    return s;
//}
//int main()
//{
//    int a1[] = { 1,2,3,4,5,6,7,8,9 };
//    void* p = my_memmove(a1+2 , a1  , 4 * sizeof(a1[0]));
//    int i = 0;
//    for (i = 0; i < 9; i++)
//    {
//        printf("%d ", a1[i]);
//    }
//    return 0;
//}

//#include<stdio.h>

//int main()
//{
//    int a = 1;
//    char b = a;
//    if (b)
//    {
//        printf("小端");
//    }
//    else
//    {
//        printf("小端");
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int a = 0x11223344;
//
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//            char a = -1;
//          signed char b = -1;
//           unsigned char c = -1;
//            printf("a=%d,b=%d,c=%d", a, b, c);     
//    return 0;
//}
//#include <stdio.h> 
//int main()
//{    char a = 128;
//     printf("%u\n",a);
//     return 0; 
//}
//#include <stdio.h>
//#include<string.h>
//int main() 
//{    char a[1000]; 
//     int i;
//     for(i=0; i<1000; i++)
//     {
//            a[i] = -1 - i; 
//     }    
//     printf("%d", strlen(a)); 
//     return 0; 
//}

//#include <stdio.h>
//int main() 
//{    unsigned int i;   
//for(i = 9; i >= 0; i--) 
//{        printf("%u\n",i);    }  
//return 0; 
//}
//#include <stdio.h> 
//int main() 
//{    int a[4] = { 1, 2, 3, 4 };
//int *ptr1 = (int *)(&a + 1);
//int *ptr2 = (int *)((int)a + 1);
//printf("%x,%x", ptr1[-1], *ptr2);
//return 0;
// }

//#include<stdio.h>
//int my_atoi(char* a)
//{
//    int s = 0;
//    int i = 0;
//    int add = 0;;
//    while (*a)
//    {
//        add *= 10;
//        add += (*a - '0');
//        a++;
//    }
//    return add;
//}
//
//int main()
//{
//    char a[] = "123";
//
//    int b = my_atoi(a);
//    printf("%d\n", b);
//    return 0;
//}
//#include <stdio.h> 
//int main() 
//{    int n = 9;  
//     //0000 0000 0000 0000 0000 0000 0000 1001
//     //s = 0;M = 1.001;E = -126
//     float *pFloat = (float *)&n; 
//     printf("n的值为：%d\n",n);   
//     printf("*pFloat的值为：%f\n",*pFloat);
//     *pFloat = 9.0;    
//     printf("num的值为：%d\n",n);
//     printf("*pFloat的值为：%f\n",*pFloat);
//     return 0;
//}

//#include<stdio.h>
//int main()
//{
//    printf("10");
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    printf("Hello,World!");
//    return 0;
//}
//#include<stdio.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    unsigned int a[1000] = { 0 };
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int b = a[0];
//    for (int i = 0; i < n; i++)
//    {
//        a[i] = a[i + 1];
//    }
//    a[n - 1] = b;
//    int i = 0;
//    for (i = 0; i < n - 1; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    printf("%d", a[i]);
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[1005] = { 0 };
//    for (int i = 2; i <= n; i++)
//    {
//        for (int j = i; j <= n; j++)
//        {
//            if (j % i == 0)
//            {
//                if (a[j])
//                {
//                    a[j] = 0;
//                }
//                else
//                {
//                    a[j] = 1;
//                }
//            }
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (!a[i])
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int m, n;
//    scanf("%d %d", &n, &m);
//    int a[1005] = { 0 };
//    int p = n;
//    for (int i = 1; i <= n; i++)
//    {
//        a[i] = i;
//    }
//    int i = 1;
//    int k = 1;
//    int l = 0;
//    while (1)
//    {
//        if (a[i])
//        {
//            if (k == m)
//            {
//                k = 0;
//                printf("%d ", a[i]);
//                a[i] = 0;
//                l++;
//            }
//            k++;
//        }
//        i++;
//        if (i == (n + 1))
//        {
//            i = 1;
//        }
//        if (n == l)
//        {
//            break;
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//struct S {
//    unsigned int _a : 3;
//    int _b : 3;
//    int _c : 2;
//};
//int main()
//{
//    struct S s = { 6,2,1 };
//    printf("%d %d %d", s._a, s._b, s._c);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int a = 1;
//    int b = 1;
//    if (a >= b)
//        printf("1");
//    else
//    {
//        printf("2");
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    unsigned char puc[4];
//    struct tagPIM
//    {
//        unsigned char ucPim1;
//        unsigned char ucData0 : 1;
//        unsigned char ucData1 : 2;
//        unsigned char ucData2 : 3;
//    }*pstPimData;
//    pstPimData = (struct tagPIM*)puc;
//    memset(puc, 0, 4);
//    pstPimData->ucPim1 = 2;
//    pstPimData->ucData0 = 3;
//    pstPimData->ucData1 = 4;
//    pstPimData->ucData2 = 5;
//    printf("%02x %02x %02x %02x\n", puc[0], puc[1], puc[2], puc[3]);
//    return 0;
//}
//#include <stdio.h>
//union Un
//{
//    short s[7];
//    int n;
//};
//int main()
//{
//    printf("%zd\n", sizeof(union Un));
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    union
//    {
//        short k;
//        char i[2];
//    }*s, a;
//    s = &a;
//    s->i[0] = 0x39;
//    s->i[1] = 0x38;
//    printf("%x\n", a.k);
//    return 0;
//}
//#include<stdio.h>
//union S
//{
//    int a ;
//    char b;
//};
//int main()
//{
//    union S s = { 0 };
//    s.a = 1;
//    if (s.b)
//    {
//        printf("小端");
//    }
//    else
//    {
//        printf("大端");
//    }
//    return 0;
//}

//#include<stdio.h>
//int Li(int i)
//{
//    int add = 0;
//    int k = i;
//    int l = 10;
//    i /= 10;
//    while (i)
//    {
//        add += (k % l) * (k / l);
//        l *= 10;
//        i /= 10;
//    }
//    if (k == add)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//int main()
//{
//    for (int i = 9999; i <= 99999; i++)
//    {
//        if (Li(i))
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n;
//    int a[60];
//    int num;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    scanf("%d", &num);
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] != num)
//            printf("%d ", a[i]);
//    }
//    return 0;
//}

//#include<stdio.h>
//enum S {
//    a = 4,
//    b,
//    c = 8,
//    d
//};
//int main()
//{
//    printf("%d ", a);
//    printf("%d ", b);
//    printf("%d ", c);
//    printf("%d ", d);
//
//    return 0;
//}
//#include<stdio.h>
//enum S
//{
//    a = 1,b,c,d,e
//};
//int main()
//{
//    printf("%d", a);
//    return 0;
//}

//#include<string.h>
//#include <stdlib.h>
//int* getConcatenation(int* nums, int numsSize, int* returnSize) {
//    *returnSize = 2 * numsSize;
//    int* ans = (int*)malloc(sizeof(int) * (*returnSize));
//    if (ans == NULL)
//    {
//        return 0;
//    }
//    memcpy(ans, nums, sizeof(int) * numsSize);
//    memcpy(ans + numsSize, nums, sizeof(int) * numsSize);
//    return ans;
//}
//#include <stdio.h>
//#include <stdlib.h>
//
//int main() {
//    int rows = 3;
//    int cols = 5;
//
//    // 分配内存以存储3*5的整型二维数组
//    int** array = (int**)malloc(rows * sizeof(int*));
//    if (array == NULL) {
//        printf("Memory allocation failed. Exiting...");
//        return 1;
//    }
//
//    for (int i = 0; i < rows; i++) {
//        array[i] = (int*)malloc(cols * sizeof(int));
//        if (array[i] == NULL) {
//            printf("Memory allocation failed. Exiting...");
//            return 1;
//        }
//    }
//
//    // 对二维数组赋值
//    int count = 1;
//    for (int i = 0; i < rows; i++) {
//        for (int j = 0; j < cols; j++) {
//            array[i][j] = count++;
//        }
//    }
//
//    // 访问二维数组内容
//    printf("二维数组内容：\n");
//    for (int i = 0; i < rows; i++) {
//        for (int j = 0; j < cols; j++) {
//            printf("%d ", array[i][j]);
//        }
//        printf("\n");
//    }
//
//    // 释放内存
//    for (int i = 0; i < rows; i++) {
//        free(array[i]);
//    }
//    free(array);
//
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    FILE* pFile;
//    pFile = fopen("example.txt", "wb");
//    fputs("This is an apple.", pFile);
//    fseek(pFile, 9, SEEK_SET);
//    fputs(" sam", pFile);
//    fclose(pFile);
//    return 0;
//}
//#include <stdio.h>
//
//int main() {
//    FILE* input_file, * output_file;
//    char c;
//
//    // 打开要读取的文件
//    input_file = fopen("data.txt", "r");
//    if (input_file == NULL) {
//        perror("Error opening input file");
//        return 1;
//    }
//
//    // 打开要写入的文件
//    output_file = fopen("data_copy.txt", "w");
//    if (output_file == NULL) {
//        perror("Error opening output file");
//        fclose(input_file);
//        return 1;
//    }
//
//    // 从输入文件读取数据并写入输出文件
//    while ((c = fgetc(input_file)) != EOF) {
//        fputc(c, output_file);
//    }
//
//    // 关闭文件
//    fclose(input_file);
//    fclose(output_file);
//
//    return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//int main()
//{
//    int a = atoi("  -1231");
//    printf("%d", a);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[1005] = { 0 };
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int max = 1;
//    int b = a[0];
//    for (int i = 1; i < n; i++)
//    {
//        if (b < a[i])
//        {
//            max = i + 1;
//            b = a[i];
//        }
//    }
//    printf("%d", max);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[30];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n - i - 1; j++)
//        {
//            if (a[j] < a[j + 1])
//            {
//                int t = a[j];
//                a[j] = a[j + 1];
//                a[j + 1] = t;
//            }
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        printf("%d\n", a[i]);
//    }
//    return 0;
//}

//#include<stdio.h>
//int my_su(int i)
//{
//    for (int k = 2; k < i; k++)
//    {
//        if (i % k == 0)
//        {
//            return 0;
//        }
//    }
//    return 1;
//}
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    for (int i = 2; i <= n; i++)
//    {
//        if (my_su(i))
//        {
//            printf("%d\n", i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int my_same(int a[], int n, int m)
//{
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] == m)
//        {
//            count++;
//        }
//    }
//    return count;
//}
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[105] = { 0 };
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int m = 0;
//    scanf("%d", &m);
//    int k = my_same(a, n, m);
//    printf("%d", k);
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int count = 0;
//    int a[11];
//    for (int i = 0; i < 10; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    int n = 0;
//    scanf("%d", &n);
//    for (int i = 0; i < 10; i++)
//    {
//        if (a[i] <= (n + 30))
//        {
//            count++;
//        }
//    }
//    printf("%d", count);
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int a[1005], b[1005];
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d %d", &a[i], &b[i]);
//    }
//    int count = 1;
//    int num = 1;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n - i - 1; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                int t = a[j];
//                int k = b[j];
//                a[j] = a[j + 1];
//                b[j] = b[j + 1];
//                a[j + 1] = t;
//                b[j + 1] = k;
//            }
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        int t = i;
//        for (int j = i; j < n; j++)
//        {
//            if (b[t] <= a[j + 1])
//            {
//                t = j + 1;
//                num++;
//            }
//        }
//        if (num > count)
//        {
//            count = num;
//        }
//        num = 1;
//    }
//    printf("%d", count);
//    return 0;
//}

//#include<stdio.h>
//struct act {
//    int B;
//    int E;
//    int T;
//}a[5008];
//int main()
//{
//    int m, n;
//    scanf("%d %d", &n, &m);
//    for (int i = 0; i < m; i++)
//    {
//        scanf("%d %d %d", a[i].B, a[i].E, a[i].T);
//    }
//    
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    //打开文件：
//    FILE* pf = fopen("test.txt", "r");
//    if (pf == NULL)
//    {
//        perror("fopen");
//        return 1;
//    }
//    //写文件：
//    fputs("Hello world\n", pf);
//    //读文件：
//    char arr[20] = "xxxxxxxxxxxxx";
//    while (fgets(arr, 7, pf) != NULL)
//    {
//        printf("%s", arr);
//    }
//    //关闭文件：
//    fclose(pf);
//    pf = NULL;
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    fscanf(stdin, "%d", &a);
//    fprintf(stdout, "%d", a);
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//	int arr[5] = { 0 };
//
//	FILE* pf = fopen("test.txt", "rb");
//	if (pf == NULL)
//	{
//		perror("fopen");
//		return 1;
//	}
//	//读数据-以二进制的形式写进去的
//	int i = 0;
//	while (fread(&arr[i], sizeof(int), 1, pf))
//	{
//		printf("%d ", arr[i]);
//		i++;
//	}
//
//	fclose(pf);
//	pf = NULL;
//
//	return 0;
//}
//#include"stdio.h"
//#define M 90
//int main()
//{
//    #if M>20
//        printf("a");
//    #endif
//        return 0;
//}
//#include<stdio.h>
//#define 
//int main()
//{
//
//    return 0;
//}
//#include <stdio.h>
//
//#define offsetof(type, member) ((size_t) &((type *)0)->member)
//
//struct TestStruct {
//    int a;
//    char b;
//    double c;
//};
//
//int main() {
//    size_t offset_a = offsetof(struct TestStruct, a);
//    size_t offset_b = offsetof(struct TestStruct, b);
//    size_t offset_c = offsetof(struct TestStruct, c);
//
//    printf("Offset of 'a': %zu\n", offset_a);
//    printf("Offset of 'b': %zu\n", offset_b);
//    printf("Offset of 'c': %zu\n", offset_c);
//
//    return 0;
//}
//#include <stdio.h>
//
//// 定义一个宏，用于交换一个整数的奇数位和偶数位
//#define SWAP_ODD_EVEN_BITS(x) (((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1))
//
//int main() {
//    unsigned int num = 0b10101010; // 原始整数
//    printf("原始整数: %u\n", num);
//
//    unsigned int swapped = SWAP_ODD_EVEN_BITS(num);
//    printf("交换后的整数: %u\n", swapped);
//
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int a, b;
//    a = b = 1;
//    printf("%d %d", a, b);
//    return 0;
//}
//#include<stdio.h>
//
////int main()
////{
////    char arr[10] = { 0 };
////    scanf("%s", arr);
////    printf("%s", arr);
//    return 0;
//}

//typedef struct p {
//    int a;
//    int b;
//}pn;
//
//typedef pn s;
//
//typedef struct book {
//    s arr[10];
//}o;
//
//#include<stdio.h>
//
//int main()
//{
//    o an;
//    s bn;
//    an.arr[0].a = 1;
//    an.arr[0].b = 1;
//    an.arr[1].b = 2;
//    an.arr[1].b = 2;
//    s t = an.arr[0];
//    an.arr[0] = an.arr[1];
//    an.arr[1] = t;
//    printf("%d", an.arr[0].b);
//    return 0;
//}
// 
// #include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//
//// 定义一个结构体
//struct Person {
//    char name[50];
//    int age;
//};
//
//int main() {
//    // 创建一个结构体实例
//    struct Person person = { "Alice", 30 };
//
//    // 打开文件以进行写入
//    FILE* file = fopen("people.txt", "w");
//    if (file == NULL) {
//        fprintf(stderr, "Failed to open file for writing.\n");
//        return 1;
//    }
//
//    // 将结构体的内容写入文件
//    fprintf(file, "Name: %s\nAge: %d\n", person.name, person.age);
//
//    // 关闭文件
//    fclose(file);
//
//    printf("Data has been written to people.txt file successfully.\n");
//
//    return 0;
//}

//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_PEOPLE 100 // 假设最多有100条记录
//
//// 定义一个结构体
//struct Person {
//    char name[50];
//    int age;
//};
//
//int main() {
//    // 打开文件以进行读取
//    FILE* file = fopen("peopl.txt", "r");
//    if (file == NULL) {
//        fprintf(stderr, "Failed to open file for reading.\n");
//        return 1;
//    }
//
//    struct Person peopl[MAX_PEOPLE]; // 创建结构体数组
//    int count = 0; // 计数变量，记录读取的人数
//
//    int k = fscanf(file, "Name: %49s Age: %d\n", peopl[count].name, &peopl[count].age);
//    printf("%d", k);
//    // 使用循环读取文件中的每条记录
//    //while (fscanf(file, "Name: %49s Age: %d\n", peopl[count].name, &peopl[count].age) == 2) {
//    //    count++;
//    //    if (count >= MAX_PEOPLE) {
//    //        break; // 如果达到数组容量上限，则停止读取
//    //    }
//    //}
//
//    // 关闭文件
//    fclose(file);
//
//    // 输出读取到的内容
//    for (int i = 0; i < count; i++) {
//        printf("%s %d\n", peopl[i].name, peopl[i].age);
//    }
//
//    return 0;
//}

//void PrintN(int N)
//{
//    for (int i = 1; i < N; i++)
//    {
//        printf("%d\n", i);
//    }
//    printf("%d", N);
//}

//#include<math.h>
//double f(int n, double a[], double x)
//{
//    double add;
//    for (int i = 0; i <= n; i++)
//    {
//        add += a[i] * pow(x, i);
//    }
//    return add;
//}

//int Sum(int List[], int N)
//{
//    int add = 0;
//    for (int i = 0; i < N; i++)
//    {
//        add += List[i];
//    }
//    return add;
//}

//ElementType Average(ElementType S[], int N)
//{
//    ElementType aver;
//    ElementType add = 0;
//    for (int i = 0; i < N; i++)
//    {
//        add += S[i];
//    }
//    aver = add / N;
//    return aver;
//}

//ElementType Max(ElementType S[], int N)
//{
//    ElementType max = S[0];
//    for (int i = 0; i < N; i++)
//    {
//        if (max < S[i])
//        {
//            max = S[i];
//        }
//    }
//    return max;
//}

//#include <stdio.h>
//#include <stdlib.h>
//
//typedef struct Node* PtrToNode;
//struct Node {
//    int Data; /* 存储结点数据 */
//    PtrToNode Next; /* 指向下一个结点的指针 */
//};
//typedef PtrToNode List; /* 定义单链表类型 */
//
//int FactorialSum(List L);
//
//int main()
//{
//    int N, i;
//    List L, p;
//
//    scanf("%d", &N);
//    L = NULL;
//    for (i = 0; i < N; i++) {
//        p = (List)malloc(sizeof(struct Node));
//        scanf("%d", &p->Data);
//        p->Next = L;  L = p;
//    }
//    printf("%d\n", FactorialSum(L));
//
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//int FactorialSum(List L)
//{
//    int add = 0;
//    List mm = L;
//    int a = 1;
//    while (mm)
//    {
//        a = 1;
//        while (mm->Data)
//        {
//            a *= mm->Data--;
//        }
//        mm = mm->Next;
//        add += a;
//    }
//    return add;
//}
//int FactorialSum(List L) {
//    int sum = 0;
//    PtrToNode current = L;
//
//    while (current != NULL) {
//        int factorial = 1;
//        int value = current->Data;
//
//         计算当前节点值的阶乘
//        for (int i = 1; i <= value; ++i) {
//            factorial *= i;
//        }
//
//         将阶乘值累加到总和中
//        sum += factorial;
//
//         移动到下一个节点
//        current = current->Next;
//    }
//
//    return sum;
//}
//#include<stdio.h>
//int main()
//{
//    int* a;
//    if (a == NULL)
//    {
//        printf("YES");
//    }
//    return 0;
//}

//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//    int src = m - 1;
//    int dst = n - 1;
//    int cop = nums1Size - 1;
//    while (src >= 0 && dst >= 0)
//    {
//        if (nums1[src] > nums2[dst])
//        {
//            nums1[cop--] = nums1[src--];
//        }
//        else
//        {
//            nums1[cop--] = nums2[dst--];
//        }
//    }
//    while (dst>=0)
//    {
//        nums1[cop--] = nums2[dst--];
//    }
//}

//int removeElement(int* nums, int numsSize, int val) {
//    int src = 0;
//    int dst = 0;
//    while (src < numsSize)
//    {
//        if (nums[src] != val)
//        {
//            nums[dst] = nums[src];
//            dst++;
//        }
//        src++;
//    }
//    return dst;
//}

//#include<math.h>
//
//#include <stdio.h>
//#include <math.h>
//
//int IsTheNumber(const int N);
//
//int main()
//{
//    int n1, n2, i, cnt;
//
//    scanf("%d %d", &n1, &n2);
//    cnt = 0;
//    for (i = n1; i <= n2; i++) {
//        if (IsTheNumber(i))
//            cnt++;
//    }
//    printf("cnt = %d\n", cnt);
//
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//int fn(int N)
//{
//    int arr[100];
//    int size = 0;
//    while (N)
//    {
//        arr[size++] = N % 10;
//        N /= 10;
//    }
//    for (int i = 0; i < size; i++)
//    {
//        for (int j = i + 1; j < size; j++)
//        {
//            if (arr[i] == arr[j])
//            {
//                return 1;
//            }
//        }
//    }
//    return 0;
//}
//
//int IsTheNumber(const int N)
//{
//    if (((int)sqrt(N) * (int)sqrt(N) != N) || (!fn(N)))
//    {
//        return 0;
//    }
//    return 1;
//}


  //Definition for singly-linked list.
//  struct ListNode {
//      int val;
//      struct ListNode *next;
//  };
// 
//typedef struct ListNode ll;
//struct ListNode* reverseList(struct ListNode* head) {
//    if (!head)
//    {
//        return head;
//    }
//    ll* a = NULL;
//    ll* b = head;
//    ll* c = b->next;
//    while (b)
//    {
//        b->next = a;
//        a = b;
//        b = c;
//        if (c)
//            c = c->next;
//    }
//    return a;
//}


  //Definition for singly-linked list.
//#include<stdlib.h>
//  struct ListNode {
//    int val;
//     struct ListNode *next;
//  };
//  typedef struct ListNode ll;
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    ll s;
//    s.next = head;
//    ll* a = &s;
//    ll* b = head;
//    while (b)
//    {
//        if (b->val == val)
//        {
//            a->next = b->next;
//            ll* k = b;
//            b = b->next;
//            free(k);
//        }
//        else
//        {
//            b = b->next;
//            a = a->next;
//        }
//    }
//    return s.next;
//}



  //Definition for singly-linked list.
//  struct ListNode {
//      int val;
//      struct ListNode *next;
//  };
//  typedef struct ListNode ll;
//struct ListNode* middleNode(struct ListNode* head) {
//    ll* n1 = head;
//    ll* n2 = head;
//    while (n2 && n2->next)
//    {
//        n1 = n1->next;
//        n2 = n2->next->next;
//    }
//    return n1;
//}

//#include<stdlib.h>
//struct ListNode {
//    int val;
//    struct ListNode* next;
//};
//typedef struct ListNode ll;
////分配内存
//ll* List_mem(int i)
//{
//    ll* k =  (ll*)malloc(sizeof(ll));
//    if (k == NULL)
//    {
//        exit(1);
//    }
//    k->val = i;
//    k->next = NULL;
//    return k;
//}
//
////创建一个链表
//ll* List_set(int n)
//{
//    ll* n1 = List_mem(1);
//    ll* n2 = n1;
//    for (int i = 2; i <= n; i++)
//    {
//        n2->next = List_mem(i);
//        n2 = n2->next;
//    }
//    n2->next = n1;
//    return n1;
//}
//
//int ysf(int n, int m) {
//    ll* mn = List_set(n);
//    ll* n1 = mn;
//    ll* n2 = n1;
//    int count = 1;//计数器
//    while (n2->next != n1)
//    {
//        n2 = n2->next;
//    }
//    while (n1->next != n1)
//    {
//        if (count == m)
//        {
//            n2->next = n1->next;
//            free(n1);
//            n1 = n2->next;
//            count = 1;
//        }
//        else
//        {
//            n2 = n2->next;
//            n1 = n1->next;
//            count++;
//        }
//    }
//    return n1->val;
//}


 // Definition for singly-linked list.
//#include<stdlib.h>
//  struct ListNode {
//      int val;
//      struct ListNode *next;
//  };
//  typedef struct ListNode ll;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    if (list1 == NULL)
//    {
//        return list2;
//    }
//    if (list2 == NULL)
//    {
//        return list1;
//    }
//    ll* n1 = list1;
//    ll* n2 = list2;
//    ll* head, * tail;
//    head = tail = NULL;
//    while (n1 && n2)
//    {
//        if (n1->val > n2->val)
//        {
//            if (head == NULL)
//            {
//                head = tail = n2;
//            }
//            else
//            {
//                tail->next = n2;
//                tail = tail->next;
//            }
//            n2 = n2->next;
//        }
//        else
//        {
//            if (head == NULL)
//            {
//                head = tail = n1;
//            }
//            else
//            {
//                tail->next = n1;
//                tail = tail->next;
//            }
//            n1 = n1->next;
//        }
//    }
//    if (n1)
//    {
//        tail->next = n1;
//    }
//    if(n2)
//    {
//        tail->next = n2;
//    }
//    return head;
//}

//#include <stdio.h>
//
//int Factorial(const int N);
//
//int main()
//{
//    int N, NF;
//
//    scanf("%d", &N);
//    NF = Factorial(N);
//    if (NF)  printf("%d! = %d\n", N, NF);
//    else printf("Invalid input\n");
//
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//int Factorial(const int N)
//{
//    if (N < 0)
//    {
//        return 0;
//    }
//    else
//    {
//        int k = N;
//        int result = 1;
//        while (k)
//        {
//            result *= k--;
//        }
//        return result;
//    }
//}

//#include <stdio.h>
//
//int Count_Digit(const int N, const int D);
//
//int main()
//{
//    int N, D;
//
//    scanf("%d %d", &N, &D);
//    printf("%d\n", Count_Digit(N, D));
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//int Count_Digit(const int N, const int D)
//{
//    if (N == 0)
//    {
//        return 1;
//    }
//    int n = N;
//    if (n < 0)
//    {
//        n = -n;
//    }
//    int count = 0;
//    while (n != 0)
//    {
//        if (n % 10 == D)
//        {
//            count++;
//        }
//        n /= 10;
//    }
//    return count;
//}

//#include <stdio.h>
//
//void Print_Factorial(const int N);
//
//int main()
//{
//    int N;
//
//    scanf("%d", &N);
//    Print_Factorial(N);
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//void Print_Factorial(const int N)
//{
//    if (N < 0)
//    {
//        printf("Invalid input");
//    }
//    else
//    {
//        int num[2600] = { 0 };//阶乘的结果可能大于int类型，所以需要创建一个数组来储存结果的每位上的数
//        int i = 1;
//        int j = 0;
//        int count = 0;
//        num[0] = 1;
//        int digit = 1;//用来储存结果有几位数
//        for (i = 2; i <= N; i++)
//        {
//            //每位数字的储存和更新：
//            for (j = 0; j < digit; j++)
//            {
//                int t = i * num[j] + count;
//                num[j] = t % 10;
//                count = t / 10;
//            }
//            //若原来的位数不够储存结果：
//            while (count)
//            {
//                num[j++] = count % 10;
//                count /= 10;
//                digit++;
//            }
//        }
//        //将每位数字都打印出来：
//        for (int j = digit - 1; j >= 0; j--)
//        {
//            printf("%d", num[j]);
//        }
//    }
//}

//#include <stdio.h>
//
//#define MAXN 10
//typedef float ElementType;
//
//ElementType Median(ElementType A[], int N);
//
//int main()
//{
//    ElementType A[MAXN];
//    int N, i;
//
//    scanf("%d", &N);
//    for (i = 0; i < N; i++)
//        scanf("%f", &A[i]);
//    printf("%.2f\n", Median(A, N));
//
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//typedef ElementType e;
//void Sort1(e a[],int start, int end)
//{
//    if (start >= end)
//    {
//        return;
//    }
//    int left = start;
//    int right = end;
//    e key = a[start];
//    while (left < right)
//    {
//        while (left < right && key <= a[right])
//        {
//            right--;
//        }
//        a[left] = a[right];
//        left++;
//        while (left < right && key >= a[left])
//        {
//            left++;
//        }
//        a[right] = a[left];
//        right--;
//    }
//    a[left] = key;
//    Sort1(a, start, left - 1);
//    Sort1(a, right + 1, end);
//}
//
//void Sort2(e a[], int N)
//{
//    for (int i = 0; i < N; i++)
//    {
//        for (int j = 0; j < N - 1 - i; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                e t = a[j];
//                a[j] = a[j + 1];
//                a[j + 1] = t;
//            }
//        }
//    }
//}
//
//typedef ElementType e;
//
//void Shell_sort(e a[], int N)
//{
//    int n = N;
//    int j;
//    for (int inc = n / 2; inc > 0; inc /= 2)
//    {
//        for (int i = inc; i < n; i++)
//        {
//            e key = a[i];
//            for (j = i - inc; j >= 0 && key <= a[j]; j -= inc)
//            {
//                a[j + inc] = a[j];
//            }
//            a[j + inc] = key;
//        }
//    }
//}
//
//
//ElementType Median(ElementType A[], int N)
//{
//    //Sort1(A, 0, N - 1);
//    //Sort2(A, N);
//    //for (int i = 0; i < N; i++)
//    //{
//    //    printf("%f ", A[i]);
//    //}
//    Shell_sort(A, N);
//    return A[N / 2];
//}


//void Print(int a[], int N)
//{
//    for (int i = 0; i < N; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    printf("\n");
//}
//
//void Shell_sort(int a[], int n) 
//{
//    int inc;
//    int j;
//    for (inc = n / 2; inc > 0; inc /= 2)
//    {
//        for (int i = 1; i < n; i++)
//        {
//            int key = a[i];
//            for (j = i - 1; j >= 0 && a[j] > key; j--)
//            {
//                a[j + 1] = a[j];
//            }
//            a[j + 1] = key;
//        }
//    }
//}
//
//int main()
//{
//    int a[] = { 7, 4, 3, 9, 6, 5, 2 };
//    Shell_sort(a, 7);
//    Print(a, 7);
//    return 0;
//}

//#include <stdio.h>
//
//int even(int n);
//
//int main()
//{
//    int n;
//
//    scanf("%d", &n);
//    if (even(n))
//        printf("%d is even.\n", n);
//    else
//        printf("%d is odd.\n", n);
//
//    return 0;
//}
//
///* 你的代码将被嵌在这里 */
//int even(int n)
//{
//    if (n % 2 == 0)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}


//#include <iostream>
//using namespace std;
//
//#define MAXSIZE 50
//typedef int KeyType;
//
//typedef  struct
//{
//    KeyType  key;
//} ElemType;
//
//typedef  struct
//{
//    ElemType* R;
//    int  length;
//} SSTable;
//
//void  Create(SSTable& T)
//{
//    int i;
//    T.R = new ElemType[MAXSIZE + 1];
//    cin >> T.length;
//    for (i = 1; i <= T.length; i++)
//        cin >> T.R[i].key;
//}
//
//int  Search_Bin(SSTable T, KeyType k);
//
//int main()
//{
//    SSTable T;  KeyType k;
//    Create(T);
//    cin >> k;
//    int pos = Search_Bin(T, k);
//    if (pos == 0) cout << "NOT FOUND" << endl;
//    else cout << pos << endl;
//    return 0;
//}
//
///* 请在这里填写答案 */
//int  Search_Bin(SSTable T, KeyType k)
//{
//    int left = 1;
//    int right = T.length;
//    int mid;
//    while (left <= right)
//    {
//        mid = (left + right) / 2;
//        if (T.R[mid].key > k)
//        {
//            right = mid - 1;
//        }
//        else if (T.R[mid].key < k)
//        {
//            left = mid + 1;
//        }
//        else
//        {
//            return mid;
//        }
//    }
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    int b = 0;
//    scanf("%d %d", &a, &b);
//    if (b >= 0)
//    {
//        int c = b / 60;
//        a += (c * 100);
//        int d = b % 60;
//        int f = (d + a % 100) % 60;
//        int e = a % 100;
//        if (e + d >= 60)
//        {
//            a += 100;
//            a = a - a % 100 + f;
//        }
//        else
//        {
//            a += f;
//        }
//        while (a >= 2400)
//        {
//            a -= 2400;
//        }
//    }
//    else
//    {
//        int c = b / 60;
//        int d = b % 60;
//        int e = a % 100;
//        a += (c * 100);
//        if (e + d < 0)
//        {
//            a -= 100;
//        }
//        else
//        {
//            a += d;
//        }
//        while (a < 0)
//        {
//            a += 2400;
//        }
//        //printf("%d", c);
//        //printf("%d", d);
//        //printf("%d", e);
//
//    }
//    printf("%03d", a);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int a = 0;
//    int b = 0;
//    scanf("%d %d", &a, &b);
//    int c = a / 100;
//    int d = a % 100;
//    int e = b + d;
//    while (e < 0)
//    {
//        c--;
//        e += 60;
//    }
//    while (c < 0)
//    {
//        c += 24;
//    }
//    while (e >= 60)
//    {
//        c++;
//        e -= 60;
//    }
//    while (c >= 24)
//    {
//        c -= 24;
//    }
//    a = c * 100 + e;
//    printf("%03d", a);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int add = 0;
//    int m = 100;
//    while (n)
//    {
//        int a = n % 10;
//        add += a * m;
//        m /= 10;
//        n /= 10;
//    }
//    printf("%d", add);
//    return 0;
//}

//#include<stdio.h>

//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//    int b = a / 16;
//    int c = a % 16;
//    int d = b * 10 + c;
//    printf("%d", d);
//    return 0;
//}

//int main()
//{
//    printf("------------------------------------\n");
//    printf("Province      Area(km2)   Pop.(10K)\n");
//    printf("------------------------------------\n");
//    printf("Anhui         139600.00   6461.00\n");
//    printf("Beijing        16410.54   1180.70\n");
//    printf("Chongqing      82400.00   3144.23\n");
//    printf("Shanghai        6340.50   1360.26\n");
//    printf("Zhejiang      101800.00   4894.00\n");
//    printf("------------------------------------\n");
//    return 0;
//}

//int main()
//{
//    double a;
//    double b;
//    char c;
//    int  d;
//    scanf("%lf %d %c %lf", &a, &d, &c, &b);
//    printf("%c %d %.2lf %.2lf", c, d, a, b);
//    return 0;
//}

//int main()
//{
//    int a, b;
//    scanf("%d:%d", &a, &b);
//    if (a >= 12)
//    {
//        if (a > 12)
//        {
//            if (a > 12 && a < 24)
//                printf("%d:%d PM", a - 12, b);
//            else if (a == 24)
//            {
//                printf("%d:%d", a - 24, b);
//            }
//
//        }
//        else if (a == 12)
//            printf("%d:%d PM", a, b);
//    }
//    else
//    {
//        printf("%d:%d AM", a, b);
//    }
//    return 0;
//}

//#include<stdio.h>

//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//    if (a > 60)
//    {
//        printf("Speed: %d - Speeding", a);
//    }
//    else
//    {
//        printf("Speed: %d - OK", a);
//    }
//    return 0;
//}

//int main()
//{
//    int a, b, c;
//    scanf("%d %d %d", &a, &b, &c);
//    if (a == b)
//    {
//        printf("C");
//    }
//    else if (a != b)
//    {
//        if (a == c)
//        {
//            printf("B");
//        }
//        else if (b == c)
//        {
//            printf("A");
//        }
//    }
//    return 0;
//}

//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    double add = 0;
//    if (a >= 5)
//    {
//        int c = 50;
//        if (b > 40)
//        {
//            add = c * 40 + 1.5 * c * (b - 40);
//        }
//        else
//        {
//            add = c * b;
//        }
//        printf("%.2lf", add);
//    }
//    else
//    {
//        int c = 30;
//        if (b > 40)
//        {
//            add = c * 40 + 1.5 * c * (b - 40);
//        }
//        else
//        {
//            add = c * b;
//        }
//        printf("%.2lf", add);
//    }
//    return 0;
//}

//int main()
//{
//    int a = 0;
//    scanf("%d", &a);
//    double n;
//    if (a > 15)
//    {
//        n = 2.5 * a - 17.5;
//    }
//    else
//    {
//        n = (4 * a) / 3.0;
//    }
//    printf("%.2lf", n);
//    return 0;
//}

//int main()
//{
//    int a, b;
//    char c;
//    scanf("%d %c %d", &a, &c, &b);
//    int d = 0;
//    switch (c)
//    {
//    case '+':
//        d = a + b;
//        printf("%d", d);
//
//        break;
//    case '-':
//        d = a - b;
//        printf("%d", d);
//
//        break;
//
//    case '*':
//        d = a * b;
//        printf("%d", d);
//
//        break;
//
//    case '/':
//        d = a / b;
//        printf("%d", d);
//
//        break;
//
//    case '%':
//        d = a % b;
//        printf("%d", d);
//
//        break;
//
//    default:
//        printf("ERROR");
//    }
//    return 0;
//}

#include<stdio.h>
//int main()
//{
//    double a, b, c, d;
//    scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
//    if (d < a)
//    {
//        printf("BW-Solid");
//    }
//    else if (d > a)
//    {
//        printf("R-Hollow");
//    }
//    else if (d == a)
//    {
//        printf("R-Cross");
//    }
//    if (c < a && c < d && b>a && b>d)
//    {
//        printf(" with Lower Shadow and Upper Shadow");
//    }
//    else if (c < a && c < d)
//    {
//        printf(" with Lower Shadow");
//    }
//    else if (b > a && b > d)
//    {
//        printf(" with Upper Shadow");
//    }
//    return 0;
//}

//int main()
//{
//    int a, b;
//    scanf("%d %d", &a, &b);
//    int sum = 0;
//    int count = 0;
//    for (int i = a; i <= b; i++)
//    {
//        if (count == 5)
//        {
//            count = 0;
//            printf("\n");
//        }
//        printf("%5d", i);
//        sum += i;
//        count++;
//    }
//    printf("\nSum = %d", sum);
//    return 0;
//}

//int main()
//{
//    double a = 0;
//    scanf("%lf", &a);
//    double sum = 1;
//    double b = 0;//分子
//    double c = 1;//分母
//    double m = 1;
//    double n = 1;
//    double d = 1;
//    while (d >= a)
//    {
//        b++;
//        c += 2;
//        m *= b;
//        n *= c;
//        d = m / n;
//        sum += d;
//    }
//    printf("%.6lf", 2*sum);
//    return 0;
//}

//#include<stdio.h>
//
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int num = 0;
//    int ll = n + 3;
//    int arr[300];
//    int sz = 0;
//    for (int i = n; i <= ll; i++)
//    {
//        for (int j = n; j <= ll; j++)
//        {
//            if (j == i)
//            {
//                ;
//            }
//            else
//            {
//                for (int k = n; k <= ll; k++)
//                {
//                    if (j == k || i == k)
//                    {
//                        ;
//                    }
//                    else
//                    {
//                        arr[sz] = i * 100 + j * 10 + k;
//                        sz++;
//                    }
//                }
//            }
//        }
//    }
//    int count = 0;
//    for (int i = 0; i < sz; i++)
//    {
//        if (count == 0)
//        {
//            printf("%d", arr[i]);
//            count++;
//        }
//        else
//        {
//            printf(" %d", arr[i]);
//            count++;
//        }
//        if (count == 6)
//        {
//            count = 0;
//            printf("\n");
//        }
//    }
//    return 0;
//}

#include<stdio.h>
#include<Windows.h>
//int main()
//{
//    system("mode con cols=100 lines=30");//设置控制台大小
//    system("title 贪吃蛇");//控制控制台标题
//    system("pause");
//
//    //获得控制台句柄
//    HANDLE output = NULL;
//    output = GetStdHandle(STD_OUTPUT_HANDLE);//获取控制台标准输出的句柄，并且将返回值赋给output
//
//    CONSOLE_CURSOR_INFO con = { 0 };//创建一个包含光标信息的结构体（光标大小和显示）
//    GetConsoleCursorInfo(output, &con);//获取光标的句柄，储存到conz中
//
//    //改变光标信息
//    con.dwSize = 50;
//    con.bVisible = true;
//
//    //根据信息设置光标
//    SetConsoleCursorInfo(output, &con);
//
//    return 0;
//}

//void set_coor(short x, short y)
//{
//    //获得控制台句柄
//    HANDLE output = NULL;
//    output = GetStdHandle(STD_OUTPUT_HANDLE);//获取控制台标准输出的句柄，并且将返回值赋给output
//
//    COORD coor = { x, y };
//    SetConsoleCursorPosition(output, coor);
//}
//
//int main()
//{
//    for (int i = 0; i < 29; i++)
//    {
//        set_coor(i, 0);
//        printf("0");
//    }
//    for (int i = 1; i < 10; i++)
//    {
//        set_coor(28, i);
//        printf("0");
//    }
//    for (int i = 1; i < 10; i++)
//    {
//        set_coor(0, i);
//        printf("0");
//    }
//    for (int i = 1; i < 29; i++)
//    {
//        set_coor(i, 9);
//        printf("0");
//    }
//    return 0;
//}

//#include<winuser.h>
//int main()
//{
//    while (1)
//    {
//        if ((GetAsyncKeyState(0x35) & 1) == 1)
//        {
//            printf("5被按过\n");
//        }
//        else if ((GetAsyncKeyState(0x35) & 1) == 0)
//        {
//            printf("5没有被按过\n");
//        }
//    }
//    return 0;
//}

//#include<winuser.h>
//int main()
//{
//    short ret = GetAsyncKeyState(0x35);
//    if ((ret & 1) == 1)
//    {
//        printf("5被按过/n");
//    }
//    else
//    {
//        printf("5没有被按过\n");
//    }
//    return 0;
//}

//#include<windows.h>
//int main()
//{
//    while (1)
//    {
//        if ((GetAsyncKeyState(0x35) & 1) == 1)
//        {
//            printf("5被按过\n");
//        }
//        else
//        {
//            printf("5没有被按过\n");
//        }
//
//        Sleep(1000); //就是CPU执行代码太快了，需要加休眠函数来延迟一下
//    }
//    return 0;
//}

//#include <stdio.h>
//#include <windows.h>
//#define KEY_PRESS(VK) ( (GetAsyncKeyState(VK) & 0x1) ? 1 : 0 )
//int main()
//{
//    while (1)
//    {
//        if (KEY_PRESS(0x30))
//        {
//            printf("0\n");
//        }
//        else if (KEY_PRESS(0x31))
//        {
//            printf("1\n");
//        }
//        else if (KEY_PRESS(0x32))
//        {
//            printf("2\n");
//        }
//        else if (KEY_PRESS(0x33))
//        {
//            printf("3\n");
//        }
//        else if (KEY_PRESS(0x34))
//        {
//            printf("4\n");
//        }
//        else if (KEY_PRESS(0x35))
//        {
//            printf("5\n");
//        }
//        else if (KEY_PRESS(0x36))
//        {
//            printf("6\n");
//        }
//        else if (KEY_PRESS(0x37))
//        {
//            printf("7\n");
//        }
//        else if (KEY_PRESS(0x38))
//        {
//            printf("8\n");
//        }
//        else if (KEY_PRESS(0x39))
//        {
//            printf("9\n");
//        }
//    }
//    return 0;
//}

#include<stdio.h>
//int main()
//{
//    ////system("mode con cols=30 lines=30");
//    //system("title 贪吃蛇");
//    ////system("pause");
//    return 0;
//}
//int main()
//{
//    HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
//    //影藏光标操作 
//    CONSOLE_CURSOR_INFO CursorInfo;
//    GetConsoleCursorInfo(hOutput, &CursorInfo);//获取控制台光标信息 
//    CursorInfo.bVisible = false; //隐藏控制台光标 
//    SetConsoleCursorInfo(hOutput, &CursorInfo);//设置控制台光标状态 
//    return 0;
//}
//int main()
//{
//    COORD pos = { 10, 5 };
//    HANDLE hOutput = NULL;
//    //获取标准输出的句柄(⽤来标识不同设备的数值) 
//    hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
//    //设置标准输出上光标的位置为pos 
//    SetConsoleCursorPosition(hOutput, pos);
//    getchar();
//    return 0;
//}
//#include <stdio.h>
//#include <windows.h>
//#define KEY_PRESS(VK) ( (GetAsyncKeyState(VK) & 0x1) ? 1 : 0 )
//
//int main()
//{
//    while (1)
//    {
//        if (KEY_PRESS(0x30))
//        {
//            printf("0\n");
//        }
//        else if (KEY_PRESS(0x31))
//        {
//            printf("1\n");
//        }
//        else if (KEY_PRESS(0x32))
//        {
//            printf("2\n");
//        }
//        else if (KEY_PRESS(0x33))
//        {
//            printf("3\n");
//        }
//        else if (KEY_PRESS(0x34))
//        {
//            printf("4\n");
//        }
//        else if (KEY_PRESS(0x35))
//        {
//            printf("5\n");
//        }
//        else if (KEY_PRESS(0x36))
//        {
//            printf("6\n");
//        }
//        else if (KEY_PRESS(0x37))
//        {
//            printf("7\n");
//        }
//        else if (KEY_PRESS(0x38))
//        {
//            printf("8\n");
//        }
//        else if (KEY_PRESS(0x39))
//        {
//            printf("9\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<locale.h>
//
////1.设置光标的坐标 
//void Set_Con(int x, int y)
//{
//    COORD pos = { x, y };
//    HANDLE hOutput = NULL;
//    //获取标准输出的句柄(⽤来标识不同设备的数值) 
//    hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
//    //设置标准输出上光标的位置为pos 
//    SetConsoleCursorPosition(hOutput, pos);
//}
//
////2.规则说明界面
//void Print_rule()
//{
//    Set_Con(15, 10);
//    printf("请用↑. ↓. ←. →控制蛇移动的方向，F3为加速，F4为减速，加速会获得更高的分数。\n\n\n\n\n\n\n");
//    system("pause");
//    //system("cls");
//}
//
////3.绘制地图
//void Print_wall()
//{
//    for (int i = 0; i < 29; i++)
//    {
//        wprintf(L"%lc", L'□');
//    }
//    Set_Con(0, 26);
//    for (int i = 0; i < 29; i++)
//    {
//        wprintf(L"%lc", L'□');
//    }
//    for (int i = 1; i < 26; i++)
//    {
//        Set_Con(0, i);
//        wprintf(L"%lc", L'□');
//    }
//    for (int i = 1; i < 26; i++)
//    {
//        Set_Con(56, i);
//        wprintf(L"%lc", L'□');
//    }
//}
//
//
//int main()
//{
//    //适配到本地
//    setlocale(LC_ALL, "");
//    wchar_t ch = L'□';
//    wprintf(L"%lc", ch);
//    return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int n, u, d;
//    scanf("%d %d %d", &n, &u, &d);
//    int hight = 0;
//    int time = 0;
//    while (hight < n)
//    {
//        if (hight != 0)
//        {
//            time += 1;
//            hight -= d;
//        }
//        time += 1;
//        hight += u;
//    }
//    printf("%d", time);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    char a[30];
//    printf("%d", sizeof(a));
//    return 0;
//}

//#include<stdio.h>
//#include<math.h>
//double eval(double x, double a3, double a2, double a1, double a0)
//{
//    return (a3 * pow(x, 3) + a2 * pow(x, 2) + a1 * x + a0);
//}
//
//double fn(double a3, double a2, double a1, double a0, double left, double right, double threshold)
//{
//    while (right - left > threshold)
//    {
//            double mid = (left + right) / 2;
//            double fmid = eval(mid, a3, a2, a1, a0);
//            double fleft = eval(left, a3, a2, a1, a0);
//            double fright = eval(right, a3, a2, a1, a1);
//            if (fright * fleft)
//            {
//                if (fmid == 0)
//                {
//                    return mid;
//                }
//
//                if (fmid * fleft >= 0)
//                {
//                    left = mid;
//                }
//                else if (fmid * fright >= 0)
//                {
//                    right = mid;
//                }
//            }
//    }
//    return (left + right) / 2;
//}
//
//int main()
//{
//    double num[4] = { 0 };
//    for (int i = 0; i < 4; i++)
//    {
//        scanf("%lf", &num[i]);
//    }
//    double left = 0;
//    double right = 0;
//    scanf("%lf %lf", &left, &right);
//    double ret = fn(num[0], num[1], num[2], num[3], left, right, 0.0001);
//    printf("%.2lf", ret);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int a = 1;
//    if (a == 1)
//    {
//        printf("0\n");
//    }
//    else if (a > 0)
//    {
//        printf("1\n");
//    }
//    return 0;
//

//#include <stdio.h>
//#include <string.h>
//
//int getNumber(char* word) {
//    if (strcmp(word, "zero") == 0) return 0;
//    if (strcmp(word, "one") == 0) return 1;
//    if (strcmp(word, "two") == 0) return 2;
//    if (strcmp(word, "three") == 0) return 3;
//    if (strcmp(word, "four") == 0) return 4;
//    if (strcmp(word, "five") == 0) return 5;
//    if (strcmp(word, "six") == 0) return 6;
//    if (strcmp(word, "seven") == 0) return 7;
//    if (strcmp(word, "eight") == 0) return 8;
//    if (strcmp(word, "nine") == 0) return 9;
//    return -1; // Error: Invalid word
//}
//
//int main() {
//    char word1[10], word2[10];
//    while (1) {
//        scanf("%s %*s %s", word1, word2);
//        if (strcmp(word1, "zero") == 0 && strcmp(word2, "eo") == 0) break;
//
//        int num1 = getNumber(word1);
//        int num2 = getNumber(word2);
//        printf("%d\n", num1 + num2);
//    }
//    return 0;
//}

#include<stdio.h>



int main() 
{

    return 0;
}